[알고리즘 정리] 깊이 우선 탐색(DFS)

April 25, 2020

Depth First Search

DFS는 그래프를 순회하기 위해 사용하는 알고리즘 전략으로, 한 노드로부터 시작해서 자식노드를 계속 따라가며 더 이상 자식노드가 나타나지 않을 때까지 진행하고 더 이상 자녀가 없을 때는 왔던 길을 다시 거슬러 올라가며 탐색하지 않은 다른 노드들을 같은 방법으로 순회하는 알고리즘이다.

Algorithm Steps

DFS 를 적용하기 위한 다양한 방법이 있지만 강의에서 소개된 방법은 색깔을 통해 각 노드의 상태를 표현하고, 해당 노드가 발견된 시간(실제 시간을 기록하진 않는다), 탐색이 끝난 시간을 기록하는 방법으로 노드들을 순회한다.

Node State

DFS가 탐색할 각 노드 혹은 vertex 는 다음 세개 중 하나의 색깔로 상태를 나타낸다.

White : 아직 발견되지 않은 노드
Gray : 발견은 되었지만 아직 해당 노드의 모든 자식과 자손 노드들을 탐색하지 않은 노드
Black : 해당 노드로 부터 파생된 모든 자손 노드들의 탐색이 끝난 노드

가장 초기에는 대상이 되는 그래프의 모든 노드들이 흰색으로 초기화 되어 있을 것이다.

Timestamp

각 노드들은 색깔과 더불어서 두 종류의 timestamp를 가지게 된다. 여기서 timestamp는 실제 시간이 아니라 처리가 끝난 순서를 기록하게 된다.

d[v] : discorvery time. 어떤 노드가 발견된 시간, 즉 color 상태가 white 이었다가 gray 가 된 순간을 기록한다.
f[v] : finish time. 어떤 노드의 하위 노드들의 탐색이 모두 끝나고 해당 노드로 다시 돌아온 시간 즉 color 상태가 gray에서 black이 된 순간을 기록한다.

따라서 어떤 노드 v에 대해서 d[v]는 항상 f[v] 보다 작은 값을 가지고 있어야 한다.

Pseudo Code

DFS(V, E)
1 for each u in V
2   do color[u] = white
3 time = 0

4 for each u in V
5   do if color[u] = white
6     then DFS-VISIT(u)

위 pseudo code 는 DFS를 시작하는 노드이다. 어떤 그래프 안에 노드들이 연결되어 있지 않을 수도 있기 때문에 여러개의 트리를 DFS로 각각 탐색해야하는 경우가 있을 수도 있다. 1~2 번째 라인에서는 주어진 그래프 내에 있는 모든 노드들을 하나씩 꺼내서 그 색깔을 흰색으로 초기화 해준다. 그리고 3번째 라인에서는 전역변수로 사용되는 time 변수를 0으로 초기화해준다. 이 변수는 timestamp를 계속해서 기록하는데 사용하게 된다.

4 ~ 6째 라인에서는 각 노드들을 기준으로 트리를 만드려는 시도를 하게 되는데, 만약 모든 노드들이 다 연결되어 있다면, 트리가 만들어진 이후에 색깔이 검은색으로 변경된 상태일 것이기 때문에 더 이상 반복하지 않게된다. 만약 모든 노드들이 연결되어 있지 않다면 흰색으로 남아있는 노드가 존재한다는 것이기 때문에 새로운 트리를 만드는 시도를 반복적으로 할 수 있게 된다.

DFS-VISIT(u)
1 color[u] = gray
2 time = time + 1
3 d[u] = time

4 for each v in adj[u]
5   do if color[v] = white
6     then DFS-VISIT(v)
7 color[u] = black

8 time = time + 1
9 f[u] = time

이 함수는 시작함수로부터 전달된 시작점이 될 노드부터 트리를 만들기 시작한다. 1 ~ 3 번째 라인에서는 노드를 방문했기 때문에 일단 색깔을 gray로 변경시키고 discovery time을 기록한다. 그리고 해당노드의 adjacency list, 즉 해당 노드와 연결되어 있는 노드를 하나씩 꺼내보고 만약 그 노드가 아직 방문 되지 않은 노드라면 그 노드를 시작점으로 재귀적으로 같은 작업을 반복한다. 이렇게 하면 초기 시작 노드로부터 더 이상 자녀노드가 없을 때까지 반복적으로 노드들을 체크해줄 수 있을 것이다.