깊이 우선 탐색 (Depth-First Search)

그래프 자료구조를 탐색하는 두 가지 알고리즘이 있다.

너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이다.

 

DFS란?

깊이 우선 탐색은 그래프를 탐색할 때 시작점에 해당하는 분기를 모두 탐색하고 탐색이 끝나면 다음 분기로 넘어가 탐색을 반복하는 방법이다. BFS가 넓게 탐색했다면, DFS는 깊게 탐색하는 것이다.

 

DFS의 장점은 현재 분기에 있는 노드들만 저장하면 되기 때문에 큰 저장공간을 필요로 하지 않는다. 또한 탐색하고자 하는 노드가 시작점으로부터 깊은 곳에 있다면 더 짧은 시간에 탐색을 완료할 수 있다. 하지만 간단한 탐색의 경우 BFS보다 시간이 더 소요된다.

 

PSEUDOCODE

DFS pseudocode Introduction to algorithms 3rd Edition

 

DFS를 구현하는 방법에는 두 가지 방법이 있다.

하나는 스택(Stack)을 사용하는 것이고, 또 하나는 순환 호출을 이용하는 것이다.

 

두 방법 모두 LIFO (Last in First Out)의 방식을 사용한다. 위 방식을 사용하는 이유는 하나의 분기가 끝날 때까지 해당 분기를 탐색해야 하기 때문이다. 가장 마지막으로 입력된 노드를 꺼내고, 그 노드와 인접한 노드를 다시 스택의 가장 위에 쌓는 것이다. 위 수도 코드에서 DFS-VISIT 안쪽의 재귀 호출을 스택으로 변경하면 스택으로 구현할 수 있다.

 

BFS때와 같이 위 수도코드에서는 한 꼭짓점마다 색(color), 거리(d),  부모(π)의 세가지 정보를 가진다.

 

색은 WHITE, GRAY, BLACK의 세가지 색이 있는데 각각

WHITE = 아직 탐색되지 않은 꼭짓점

GRAY = 탐색중인 꼭짓점

BLACK = 탐색 완료된 꼭짓점

이다. 즉 WHITE는 스택에 한번도 들어가 보지 않은/순환 호출되지 않았던 꼭짓점, GRAY는 스택에 들어가 있는 /순환호출 된 꼭짓점, BLACK은 스택에 들어갔다 나온/순환호출이 완료된 꼭짓점이다.

 

거리는 시작점 s로부터 해당 꼭짓점까지의 거리를 나타낸다.

 

부모는 해당 꼭짓점을 탐색한 꼭짓점을 나타낸다.

 

위 수도코드 방식은 순환 호출 방식을 사용했다.

우선 입력 변수로 그래프 G를 입력받는다. 

 

DFS

1-3. 그래프의 모든 꼭짓점의 색(color), 부모(π)를 초기화 한다.

4. 시간을 0으로 설정한다.

5-7. 한 꼭짓점 u에 대해서 u의 색이 흰색이면 DFS-VISIT(G, v)를 실행한다.

 

DFS-VISIT(G, u)

1-3. 해당 꼭짓점 u의 색을 회색으로 지정하고 거리(호출)를 할당한다. 

4-7. 꼭짓점 u에 인접한 다른 꼭짓점 v에 대해, 그 꼭짓점 v가 하얀색이면 부모를 u로 지정하고 DFS-VISIT(G, v)를 실행한다. 

8-10. 해당 분기의 모든 호출이 끝나면, 마지막에 들어간 꼭짓점부터 색을 검정, 거리(탐색 완료)를 지정한다.

 

 

Time Complexity

V - 정점 E - 간선

Adjacency List를 이용한 그래프: O(V + E)

Adjacency Matrix를 이용한 그래프: O(V^2)

---

DFS 코드 (Python)

graph = {
    's': ['r', 'w'],
    'r': ['s', 'v'],
    'v': ['r'],
    'w': ['s', 't', 'x'],
    't': ['w', 'x', 'u'],
    'x': ['w', 't', 'u', 'y'],
    'u': ['t', 'x', 'y'],
    'y': ['x', 'u'],
}
 
def dfs(graph, s):
    
    visited = dict()
    withOutParent = list()
    parent = dict()
    stack = list()
    
    visited[s] = [0, "NIL"]
    stack.extend(graph[s])
    for i in range(0, len(graph[s])):
        parent[ graph[s][i] ] = s
 
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited[vertex] = [visited[parent[vertex]][0] + 1, parent[vertex]] #[거리, 부모]
            
            withOutParent = graph[vertex]
            withOutParent.remove(parent[vertex])
            
            for v in withOutParent:
                if v in stack:
                    withOutParent.remove(v)
            stack.extend(withOutParent)
            
            for i in range(0, len(withOutParent)):
                parent[withOutParent[i]] = vertex
            
    return visited
 
print(dfs(graph,'s'))

출력: {'x': [2, 'w'], 't': [2, 'w'], 's': [0, 'NIL'], 'r': [1, 's'], 'u': [3, 'x'], 'w': [1, 's'], 'v': [2, 'r'], 'y': [3, 'x']}

 

Simple Ver (Python)

graph_list = {
    's': set(['r', 'w']),    
    'r': set(['s', 'v']),
    'v': set(['r']),
    'w': set(['s', 't', 'x']),
    't': set(['w', 'x', 'u']),
    'x': set(['w', 't', 'u', 'y']),
    'u': set(['t', 'x', 'y']),
    'y': set(['x', 'u'])
}
def DFS(graph, root):
    visited = []
    stack = []
    stack.append(root)
    
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.append(vertex)
            stack += graph[vertex] - set(visited)
    return visited
print(DFS(graph_list, 's'))

출력: ['s', 'r', 'v', 'w', 't', 'u', 'y', 'x']