[알고리즘] DFS/BFS

DFS(Depth First Search, 깊이 우선 탐색) 

BFS(Breadth First Search, 너비 우선 탐색)

---

DFS(Depth First Search, 깊이 우선 탐색) 란

 

루트 노드 혹은 다른 임의의 노드에서 다음 분기(Branch)로 넘어가 기전에 해당 분기를 완벽하게 탐색하는 방법이며 스택(Stack) 혹은 재귀함수(Recursion)로 구현된다.

 

DFS, Wikimedia Commons

 

---

코드(Python) 

 

"""
       1
    /  |  \
   2   5   9
   |   /\  |
   3  6  8 10
  /   |
 4    7
"""

graph = {
    1: [2,5,9],
    2: [3],
    3: [4],
    4: [],
    5: [6,8],
    6: [7],
    7: [],
    8: [],
    9: [10],
    10: []
}

def recursive_dfs(v, visited = []):
    visited.append(v) # 시작 정점 방문
    for w in graph[v]:
        if not w in visited: # 방문 하지 않았으면
            visited = recursive_dfs(w, visited)
    return visited

def iterative_dfs(start_v):
    visited = []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.append(v)
            for w in graph[v]:
                stack.append(w)
    return visited

print("recursive_dfs: ", recursive_dfs(1))
print("iterative_dfs: ", iterative_dfs(1))

# 스택은 마지막에 스택에 담은 정점부터 꺼내져 방문되기 때문에
# 재귀 방식과 결과가 다름.
"""
recursive_dfs:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
iterative_dfs:  [1, 9, 10, 5, 8, 6, 7, 2, 3, 4]
"""

 

---

BFS(Breadth First Search, 너비 우선 탐색) 란

루트 노드 혹은 다른 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법이며 큐(Queue)를 사용하여 구현된다. 

 

BFS, Wikimedia Commons

 

---

코드(Python) 

 

🙌 Queue 사용

"""
       1
    /  |  \
   2   3   4
   |   /\  |
   5  6  7 8
  /   |
 9    10
"""

graph = {
    1: [2,3,4],
    2: [5],
    3: [6,7],
    4: [8],
    5: [9],
    6: [10],
    7: [],
    8: [],
    9: [],
    10: []
}

def bfs(start_v):
    visited = [start_v]
    queue = [start_v]
    while queue:
        v = queue.pop(0)
        for w in graph[v]:
            if w not in visited:
                visited.append(w)
                queue.append(w)
    return visited

print("bfs: ", bfs(1))

"""
bfs:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
"""

 

리스트 사용 시 pop(0) 은 시간 복잡도가 O(n) 이므로 좋지 않다. 따라서 리스트 보다는 양방향으로 append, pop 이 가능한 

Deque를 사용하여 문제를 풀이하는 것이 좋다. 

 

🙌 Deque 사용

from collections import deque

def bfs(start_v):
    visited = [start_v]
    deq = deque()
    deq.append(start_v)
    while deq:
        v = deq.popleft()
        for w in graph[v]:
            if w not in visited:
                visited.append(w)
                deq.append(w)
    return visited

 

---

Reference

 

[Algorithm] DFS, BFS 구현 (Python)

 

[코딩테스트 대비] DFS, BFS 정리