[알고리즘] 그래프 Graph (2) - BFS&DFS

그래프에서 '탐색'이란 노드를 순회하는 것을 말합니다. 영어로는 graph traversal이라고 합니다. 
노드의 탐색 알고리즘 중 가장 대표적인 두 가지는 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)입니다. 
아래 예제 그래프를 통해서 탐색 방식이 어떤지 자세히 알아보도록 하겠습니다. 그림은 트리처럼 생겼지만, 그래프 순회 시 cycle을 이루게 하는 edge가 추가되어도 순회하는 데에는 오류가 없을 것입니다.

출처:t.ly/ipCVv

1. 너비 우선 탐색 breadth-first search : 같은 레벨에 있는 노드, 즉 형제 노드들을 우선으로 순회

그래프의 구현은 딕셔너리로, 탐색 방법은 두 개의 리스트 자료구조를 활용할 수 있습니다. 
그래프를 구현한 딕셔너리는 아래와 같이 key에 한 노드를, value에 해당 노드에 연결된 노드를 입력해줍니다.

graph = dict()

graph['s'] = ['1', '2'] #source node
graph['1'] = ['s', '3', '4', '5']
graph['2'] = ['s', '6']
graph['3'] = ['1']
graph['4'] = ['1']
graph['5'] = ['1']
graph['6'] = ['2', '7']
graph['7'] = ['6']

너비 우선 탐색을 위해서는 두개의 큐 (파이썬에서는 리스트를 그대로 사용해도 무관)를 사용해 구현을 할 수 있습니다. 
node_traversal 리스트는 탐색하는 순서를 담을 리스트, need_visit는 출력할 노드들을 담을 리스트입니다. 

1. need_visit에 탐색을 시작할 노드인 source node를 지정하면
2. node_travelsal 리스트에 해당 노드가 추가된 뒤
3. source node와 인접한 노드 목록인 value들을 need_visit 에 추가합니다.
4. need_visit은 큐이므로 앞에서부터 node_traversal에 없는 값들만 node_traversal에 추가해줍니다.

def bfs(graph, source_node):
    node_traversal = []
    need_visit = []
    need_visit.append(source_node)
    
    while need_visit: #방문이 필요한 리스트가 빌 때까지 순회
        node = need_visit.pop(0) # queue 처럼 동작 - 0 번의 위치 데이터를 뽑으면 재정렬되어 다음 데이터가 다시 0번이 됨
        if node not in node_traversal:
            node_traversal.append(node)
            need_visit.extend() #방문이 필요한 리스트 뒤에 추가해줌
            
    return node_traversal #순서대로 방문된 노드들을 출력

BFS 시간 복잡도 : while문이 노드 수 $V \times $ 엣지 수 $E$ 만큼 반복되므로 $ N(E+V) $ 

2. 깊이 우선 탐색 depth-first search : 한 노드의 child node를 우선으로 순회

출처:t.ly/xqpY

위 그림처럼 깊이 우선 탐색에서는 need_visit 을 스택으로 구현하며, 나머지는 DFS와 같습니다.
스택으로 구현하는 이유는 Last in First out 을 통해 같은 레벨의 노드가 아닌 다음 레벨의 노드를 먼저 데려오기 위해서입니다. 
아래 코드로 구현 시에는, 그림과는 달리 오른쪽 child node부터 탐색하게 됩니다. 

def dfs(graph, source_node):
    node_traversal, need_visit = list(), list()
    nned_visit.append(source_node)
    
    while need_visit:
        node = need_visit.pop() #BFS 와 다른 점: 맨 끝의 데이터 뽑기
        if node not in node_traversal:
            node_traversal.append(node)
            need_visit.extend(graph[node])
    return node_traversal

DFS 시간 복잡도 : $ N(E+V) $ 

---

풀어볼 그래프 DFS/BFS 백준 문제: 1260번, 9934번, 그래프와 순회 단계