DFS (깊이 우선 탐색) & BFS (너비 우선 탐색)

1. 그래프

정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 
그래프를 탐색하는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 의미함
-> DFS, BFS 모두 그래프를 탐색하는 방법

 

 

 

 

 

 

2. DFS (Depth - First Search)

: 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 의미함

출처 : https://developer-mac.tistory.com/64

 

1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림

 

스택 (stack) 자료구조를 사용하는 것이 핵심

-> 현재 방문한 노드에 연결된 노드를 방문해야 한 방향으로 갈 수 있음

 

- 파이썬 구현 예시

graph_list = {1: set([3, 4]),
              2: set([3, 4, 5]),
              3: set([1, 5]),
              4: set([1]),
              5: set([2, 6]),
              6: set([3, 5])}
root_node = 1


def DFS_with_adj_list(graph, root):
    visited = []
    stack = [root]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack += graph[n] - set(visited)
    return visited

print(BFS_with_adj_list(graph_list, root_node))

 

 

 

 

 

 

2. BFS (Breadth - First Search)

: 루트 노드 (혹은 다른 임의의 노드)에서 시작해 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어진 정점을 나중에 방문하는 순회 방법

-> 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 사용

 

출처 : https://developer-mac.tistory.com/64

큐 (queue) 자료구조를 사용하는 것이 핵심

pop(0)를 사용하면 시간 복잡도가 O(N)이 되므로 비효율적인 코드가 되기 때문에 deque를 사용하여 시간 복잡도를 줄일 수 있음

 

- 파이썬 구현 예시

graph_list = {1: set([3, 4]),
              2: set([3, 4, 5]),
              3: set([1, 5]),
              4: set([1]),
              5: set([2, 6]),
              6: set([3, 5])}
root_node = 1


from collections import deque

def BFS_with_adj_list(graph, root):
    visited = []
    queue = deque([root])

    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            queue += graph[n] - set(visited)
    return visited
  
print(BFS_with_adj_list(graph_list, root_node))

 

 

 

 

 

3. DFS vs BFS

 

DFS	BFS
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐를 이용해서 구현