DFS (Depth First Search) 깊이우선탐색 C++, Python 인접리스트 활용

 

그래프 순회를 하는 방법 2가지 DFS, BFS 그래프라는 자료구조안에 어떠한 값이 있는지 확인하는 용도

깊이우선탐색 DFS (Depth First Search)  stack을 이용하여 그래프를 순회하는 방법

나를 먼저 방문하고, 그 다음 (우선순위 기준으로) 인접한 노드를 차례대로 방문
* 단, 방문했던 노드는 방문하지 않는다.  (해당 노드에 대한 visited, checked 가 0이 아닌 경우)

DFS = 스택사용 = 선행관계 = 재귀호출 = 발자취

인접한 노드가 없거나 혹은 모든 인접노드를 방문을 한 경우 자신을 기준으로 이전 노드로 이동한다.(방문한 적이 없는 노드를 찾고 방문하고 되돌아오는 과정 반복) 재귀!!

v = vertex 정점
visited = 해당 노드에 방문한적이 있는지 없는 체크 용도


DFS(Graph, v, visited)  

Graph: 인접리스트 목록
v: 노드 및 간선
visited: 노드의 방문 여부를 유지 및 업데이트하기 위함(이 배열을 이용하여 인접노드의 방문 시 방문, 미방문 여부 확인 가능)

1. v를 방문했다고 처리함
2. v와 인접한 모든 노드 w(인접노드)에 대해 반복(방문하고 방문처리)
3. 이웃 노드 중 방문한적이 있는 노드라면 DFS 처리할 필요 없음, 이웃 노드 중 방문한적이 없는 노드라면 DFS 수행 (해당 노드의 인접행렬까지 처리하고와!)
4. 방문순서반환(인접한 노드가 모두 방문한적이 있다면 자신을 기준으로 이전의 v로 이동하기 위함)

 

아래의 그림은 순서가 낮은 숫자를 우선순위로 DFS한 결과

 

 

 

간단한 코드설명을 하면 

 

1. 정점과 간선의 개수를 입력받음

 

2. 정점의 간선 관계되는 값을 입력받음(간선의 개수만큼)

 

3. C++ STL Vector를 이용하여 입력받은 간선의 관계 정보 입력 당연히 1-2 와같이 1과 2라는 노드에 간선이 연결되어있다면 graph[a].push_back(b), grapth[b].push_back(a)을 통해 각각의 노드가 아 나는 어떤 노드랑 간선을 가지는 관계구나 알 수 있게

 

4. 전역변수를 이용하였기에 실제 DFS 함수는 인자 1개 시나리오상 1번부터 시작을 한다는 가정하였음.

 

5. 1번부터 접근 시 방문했다는 뜻으로 bool 타입의 visited배열의 해당 인덱스값에 true로 변환

 

6. 인접리스트를 활용하여 y = graph[x][i] 인접노드의 방문여부를 체크, 방문하지않았다 == visited[x]가 false이다. 

    false라면 너를 포함해 너의 인접하는 노드 모두 DFS를 수행하고 와라

 

7. 호출되는 순서 및 노드에 따라 printf를 통한 출력으로 DFS 수행 확인

 

8. 해당 소스코드를 알기 위해서 인접행렬, 인접리스트 개념을 잡고 소스코드로 살짝 맛본 후 직접 소스코드를 분석해서 실행해보면 도움이 될 것으로 생각됨

 

 

#include<iostream>
#include<vector>
#include<cstdio>
 
using namespace std;
 
// Global Variable
const int MAX = 100;
vector <int> graph[MAX];
bool visited[MAX];
int n, e;
 
 
void DFS(int x){
    // x부터 시작해서 DFS하여 그 순서를 출력하는 함수
    // 단, visited에 방문 기록이 있음
    printf("%d ", x);
    visited[x] = true;
 
    for (int i = 0; i<graph[x].size(); i++){
        int y = graph[x][i];
        //x와 y가 연결이 되어 있다.
 
        if (visited[y] == false){
            DFS(y);
        }
    }
}
 
int main(){
 
    scanf("%d %d", &n, &e);
 
    // 9 12
    // 1 2
    // 1 3
    // 2 3
    // 2 4 
    // 2 6
    // 3 7 
    // 4 5
    // 4 7
    // 4 8
    // 5 6
    // 7 8
    // 8 9
 
    //DFS 순서 1 2 3 7 4 5 6 8 9
 
    for (int i = 0; i < e; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
 
    }
 
    DFS(1);
    //for (int i = 1; i <= n; i++){
    //    printf("%d (%d)", i, graph[i].size());
    //    for (int j = 0; j < graph[i].size(); j++){
    //        printf("%d ", graph[i][j]);
    //    }
    //    printf("\n");
    //}
 
    return 0;
}

 

 

m, e = map(int, input().strip().split())
lists = []
visited = []
 
def dfs(x):
    visited.append(x)
    print(x)
    for i in range(len(lists[x])):
        temp = lists[x][i]
        if  temp not in visited:
            dfs(temp)
 
for i in range(m+1):
    lists.append([])
 
for i in range(e):
    a, b = map(int, input().strip().split())
    lists[a].append(b)
    lists[b].append(a)
 
dfs(1)