[알고리즘] 2-1. 깊이 우선 탐색(DFS)

DFS

DFS는 Depth-Fisrst Search. 깊이 우선 탐색이다. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

스택 자료구조를 사용하고, 최대한 깊숙히 노드를 방문하고, 끝에 도달하면 다시 돌아가서 다른 경로를 탐색한다.

 

DFS 는 다음의 동작과정이 있다:

1. 탐색 시작 노드를 스택에 삽입하고, 노드를 방문처리한다.

2. 스택 맨 위에 있는 노드에서 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고, 방문처리한다.

    방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다.

3. 2번을 계속 방문한다.(스택이 빌 때까지)

 

 

DFS의 과정

1부터 탐색을 시작한다. 1을 스택에 넣고, 방문처리를 한다.

 

'1'에서 방문하지 않은 인접 노드 '2', '3', '4'가 있다. 이 중에서 가장 작은 노드 '2'를 스택에 넣고 방문 처리한다.

 

'2'에서 방문하지 않은 인접 노드 '5'가 있다. '5'를 스택에 넣고 방문 처리한다.

'5'에서 방문하지 않은 인접 노드 '6'이 있다. '6'을 스택에 넣고 방문 처리한다.

'6'에서 방문하지 않은 노드가 없으므로 스택에서 꺼낸다. '5'와 '2' 역시 같은 이유로 꺼낸다.

다시 '1'로 돌아온다. '1'에서 방문하지 않은 노드들 중 가장 작은 노드인 '3'을 스택에 넣고, 방문처리한다.

'3'의 인접한 노드들 중 방문하지 않은 노드는 '7'이 있다. '7'을 스택에 넣고, 방문처리한다.

'7'의 인접한 노드들 중 방문하지 않은 노드는 '8'이 있다. '8'을 스택에 넣고, 방문처리한다.

'8'의 인접한 노드들 중 방문하지 않은 노드는 '4'가 있다. '4'를 스택에 넣고, 방문처리한다.

스택에 있는 노드들 중 더 이상 방문하지 않은 인접 노드가 없다. 모든 노드를 차례대로 꺼낸다.

 

노드의 위 그래프 탐색 순서(스택에 들어간 순서)는 다음과 같다:

1 -> 2 -> 5 -> 6 -> 3 -> 7 -> 8 -> 4

 

 

코드(Python)

def dfs(graph, v, visited):
    visited[v] = True#방문
    print(v, end=' ')

    for i in graph[v]:#스택 맨 위에 있는 노드에 대해서:
        if not visited[i]:#방문하지 않는 인접 노드 스택에 넣기
            dfs(graph, i, visited)
#그래프의 정보(인접 노드들)
graph = [[],
         [2, 3, 4],
         [1, 5],
         [1, 7],
         [1, 8],
         [2, 6],
         [5],
         [3, 8],
         [4, 7]]
#방문 정보
visited = [False] * 9
#1부터 깊이우선탐색
dfs(graph, 1, visited)

결과

1 2 5 6 3 7 8 4