[자료구조] DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 구현

그래프 순회(Graph Traversals)

 그래프 순회란 그래프 탐색이라고도 불리우며 그래프의 각 정점을 방문하는 과정을 말합니다.

 

 그래프의 각 정점을 방문하는 그래프 순회(Graph Traversals)는 크게 깊이 우선 탐색(DFS, Depth-First Search)와 너비 우선 탐색(BFS, Breadth-First Search)의 2가지 알고리즘이 있습니다. DFS가 일반적으로 BFS에 비해 더 널리 쓰입니다.

 

 DFS는 주로 스택으로 구현하거나 재귀로 구현하며 백트래킹을 통해 뛰어난 효용을 보입니다. 반면 BFS는 주로 큐로 구현하며, 그래프의 최단 경로를 구하는 문제 등에 사용됩니다.

 

 그래프 순회 알고리즘인 DFS와 BFS를 파이썬으로 구현해보도록 하겠습니다.

 

---

 그래프를 우선 정의합니다. 그래프를 표현하는 방법에는 크게 인접 행렬과 인접 리스트의 2가지 방법이 있습니다. 여기서는 그래프를 인접 리스트로 표현하겠습니다. 출발 노드를 키로, 노착 노드를 값으로 표현합니다. 도착 노드는 여러 개가 될 수 있으므로 리스트 형태가 됩니다.

 

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

 

---

DFS(깊이 우선 탐색)

1. 재귀 구조로 구현

def recursive_dfs(v, discovered=[]):
    discovered.append(v)
    for w in graph[v]:
        if not w in discovered:
            discovered = recursive_dfs(w, discovered)
    return discovered

 

2. 스택을 이용한 반복 구조로 구현

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

 

---

BFS(너비 우선 탐색)

1. 큐를 이용한 반복 구조로 구현

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

 

 BFS는 재귀 구현이 불가합니다.