깊이 우선 탐색과 너비 우선 탐색

미로를 빠짐없이 둘러보는 방법은 크게 두 가지입니다. 한 갈래를 끝까지 따라간 뒤 돌아와 다른 갈래로 가는 방법과, 입구에서 가까운 곳부터 한 겹씩 넓혀 가는 방법입니다. 그래프에서는 앞의 것을 깊이 우선 탐색(depth-first search, DFS), 뒤의 것을 너비 우선 탐색(breadth-first search, BFS)이라고 합니다. 이 글에서는 그래프의 모델과 표현의 인접 목록을 두 방법으로 훑어 보고, 각 방법이 어떤 질문에 답하는지 살펴봅니다.

같은 그래프, 다른 방문 순서

방향 간선 A→B, A→C, B→D, C→D가 있는 그래프를 인접 목록으로 적으면 A: [B, C], B: [D], C: [D], D: []입니다. 두 탐색 모두 A에서 출발하고, 이웃은 목록에 적힌 순서대로 봅니다. 깊이 우선 탐색은 A에서 B로 내려가고, B에서 다시 D로 내려간 뒤, 더 갈 곳이 없으면 돌아와 C를 방문하므로 순서가 A, B, D, C입니다. 너비 우선 탐색은 A에서 간선 하나로 닿는 B와 C를 먼저 처리한 뒤 D를 처리하므로 A, B, C, D입니다.

D는 B와 C 양쪽의 이웃이지만 두 탐색 모두 한 번만 방문합니다. 이미 방문한 정점을 기억해 두는 집합이 있기 때문이고, 이 집합이 없으면 사이클이 있는 그래프에서 탐색이 끝나지 않을 수도 있습니다. 두 방법을 코드로 옮기면 다음과 같습니다.

from collections import deque


def dfs(graph, start):
    seen, order = set(), []

    def visit(v):
        seen.add(v)
        order.append(v)
        for u in graph[v]:
            if u not in seen:
                visit(u)

    visit(start)
    return order


def bfs(graph, start):
    depth = {start: 0}
    queue, order = deque([start]), []
    while queue:
        v = queue.popleft()
        order.append(v)
        for u in graph[v]:
            if u not in depth:
                depth[u] = depth[v] + 1
                queue.append(u)
    return order, depth


graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(dfs(graph, "A"))
print(*bfs(graph, "A"))

['A', 'B', 'D', 'C']
['A', 'B', 'C', 'D'] {'A': 0, 'B': 1, 'C': 1, 'D': 2}

dfs는 안쪽 함수 visit이 자기 자신을 부르는 재귀로 한 갈래를 끝까지 따라갑니다. visit("D")가 끝나면 그 호출을 부른 visit("B")로 돌아가고, B에 더 볼 이웃이 없으므로 다시 visit("A")로 돌아가 남은 이웃 C를 확인합니다. 이전 정점을 다시 방문하는 것이 아니라, 호출이 끝나 돌아온 자리에서 남은 이웃을 이어서 보는 것입니다. bfs는 먼저 넣은 것을 먼저 꺼내는 큐인 deque를 쓰고, 방문 표시를 겸하는 딕셔너리 depth에 출발점에서 몇 간선 떨어졌는지를 함께 적습니다. print(*bfs(...))의 *는 돌려받은 두 값을 풀어서 print에 따로 넘깁니다.

두 함수 모두 출발점에서 닿을 수 있는 정점만 방문합니다. 그래프에 E: []를 더해도 A에서 E로 가는 간선이 없으므로 결과는 그대로입니다. 그래프의 모든 정점을 방문하려면, 방문 표시를 공유한 채 아직 방문하지 않은 정점에서 탐색을 다시 시작해야 합니다. 무방향 그래프에서 이렇게 탐색을 새로 시작한 횟수가 연결 성분의 개수입니다. 재귀를 쓰는 dfs는 아주 긴 경로가 있는 그래프에서 Python의 재귀 한도에 걸릴 수 있으므로, 큰 입력에서는 스택으로 바꾼 반복문을 씁니다. 스택과 큐로 구현하는 방법은 자료구조·알고리즘 교재의 스택과 깊이 우선 탐색 DFS와 큐와 너비 우선 탐색 BFS에서 다룹니다.

큐의 상태와 방문 표시의 시점

예제에서 BFS의 큐는 [A], [B, C], [C, D], [D], [] 순서로 바뀝니다. B를 꺼냈을 때 D를 큐에 넣으면서 바로 방문 표시를 하므로, C를 꺼냈을 때는 D가 이미 표시되어 있어 다시 넣지 않습니다. 방문 표시를 큐에서 꺼낼 때로 미루면 B와 C가 각각 D를 넣어 D가 큐에 두 번 들어갑니다. 이 예에서는 한 번 더 들어가는 것뿐이지만, 많은 정점이 같은 이웃을 가리키는 그래프에서는 큐가 불필요하게 커지고 같은 정점을 여러 번 처리하게 됩니다.

탐색 시간은 정점과 간선의 수에 비례합니다. 정점마다 한 번씩 큐에 들어가거나 visit이 불리고, 그때마다 그 정점의 인접 목록을 한 번 훑습니다. 인접 목록의 길이를 모두 더하면 방향 그래프에서는 간선 수, 무방향 그래프에서는 차수의 합인 간선 수의 두 배이므로, 전체 시간은 $O(|V|+|E|)$입니다.

너비 우선 탐색은 간선 수가 가장 적은 거리를 구한다

너비 우선 탐색이 적는 depth는 출발점에서 그 정점까지 가는 경로의 간선 수 가운데 가장 작은 값입니다. 깊이가 d인 정점을 꺼낼 때 새로 발견한 이웃은 깊이 d + 1로 큐의 맨 뒤에 붙으므로, 큐에는 언제나 깊이가 d인 정점들 뒤에 깊이가 d + 1인 정점들이 이어서 들어 있습니다. 반복 내내 참으로 남는 이 불변식 때문에 정점은 깊이가 작은 것부터 차례로 꺼내집니다. 어떤 정점 v까지 간선 d개로 가는 경로가 있다면, 그 경로에서 v 바로 앞의 정점은 간선 d − 1개로 닿으므로 더 먼저 꺼내지고, 꺼내질 때 v를 발견합니다. 그래서 v는 깊이 d보다 늦게 발견될 수 없고, 처음 발견될 때 적힌 깊이가 가장 작은 간선 수입니다. 이 성질 때문에 가중치가 없는 그래프의 최단 경로는 너비 우선 탐색으로 구합니다.

깊이 우선 탐색에는 이런 성질이 없습니다. A: [B, D], B: [C], C: [D], D: []인 그래프에서 깊이 우선 탐색은 A, B, C를 지나 D에 처음 닿지만, A에서 D로 바로 가는 간선이 있어 실제 거리는 1입니다. 깊이 우선 탐색은 대신 한 갈래를 끝까지 따라가는 성질 때문에 사이클을 찾거나 작업의 선후 순서를 정하는 데 자주 쓰입니다.

더 깊이: 너비 우선 탐색으로 이분 그래프 판정하기

그래프의 모델과 표현에서 이분 그래프에는 홀수 길이의 사이클이 없다는 것을 보았습니다. 연결된 무방향 그래프에서는 그 반대도 성립하며, 너비 우선 탐색으로 증명할 수 있습니다. 깊이가 짝수인 정점을 X, 홀수인 정점을 Y로 나누어 봅시다. 무방향 그래프에서 간선으로 이어진 두 정점은 깊이가 많아야 1 차이 나므로, 간선이 같은 쪽끼리 잇는다면 두 끝의 깊이가 같은 d입니다. 그러면 출발점에서 한쪽 끝까지 가는 d개의 간선, 그 간선, 다른 쪽 끝에서 출발점으로 돌아오는 d개의 간선이 길이 2d + 1인 닫힌 보행을 이룹니다.

길이가 홀수인 닫힌 보행에는 언제나 홀수 길이의 사이클이 들어 있습니다. 닫힌 보행에 같은 정점이 두 번 나오면 그 자리에서 닫힌 보행 두 개로 나눌 수 있고, 길이의 합이 홀수이므로 둘 중 하나는 길이가 홀수입니다. 홀수 쪽을 골라 반복되는 정점이 없어질 때까지 나누면 홀수 길이의 사이클이 남습니다. 그래서 홀수 사이클이 없는 그래프에서는 같은 쪽끼리 잇는 간선이 없고, 깊이의 홀짝으로 나눈 X와 Y가 이분 그래프의 두 쪽이 됩니다. 판정할 때는 너비 우선 탐색으로 깊이를 구한 뒤, 두 끝의 깊이의 홀짝이 같은 간선이 하나라도 있는지 보면 됩니다. 정사각형 A—B—C—D—A는 깊이가 A 0, B와 D 1, C 2라 모든 간선이 홀짝이 다른 정점을 이으므로 이분 그래프이고, 삼각형은 깊이가 같은 두 정점을 잇는 간선이 있어 이분 그래프가 아닙니다.

정리

• 깊이 우선 탐색은 한 갈래를 끝까지 따라간 뒤 돌아오고, 너비 우선 탐색은 출발점에서 가까운 정점부터 한 겹씩 방문합니다. 같은 알고리즘이라도 이웃을 보는 순서가 바뀌면 방문 순서가 바뀝니다.
• 방문 표시가 같은 정점을 두 번 처리하는 일을 막으며, 너비 우선 탐색에서는 큐에 넣을 때 표시해야 같은 정점이 큐에 여러 번 들어가지 않습니다.
• 두 탐색은 출발점에서 닿을 수 있는 정점만 방문하고, 인접 목록을 쓰면 $O(|V|+|E|)$ 시간이 걸립니다.
• 너비 우선 탐색이 처음 발견할 때 적는 깊이는 간선 수가 가장 적은 거리이고, 깊이 우선 탐색이 처음 닿는 경로는 가장 짧지 않을 수 있습니다.
• 너비 우선 탐색의 깊이를 홀짝으로 나누면 이분 그래프인지 판정할 수 있습니다.

연습 문제

1. 이웃의 순서 바꾸기

A의 이웃 목록을 [C, B]로 바꾸면 dfs와 bfs의 방문 순서는 어떻게 되나요?

2. 방문 표시를 늦게 하면

bfs를 고쳐서 큐에서 꺼낼 때 방문 표시를 하고, 이미 표시된 정점을 꺼내면 건너뛰게 했습니다. 예제 그래프에서 D는 큐에 몇 번 들어가나요?

3. 깊이 우선 탐색의 경로

A: [B, D], B: [C], C: [D], D: []인 그래프에서 dfs와 bfs는 각각 D에 어떤 경로로 처음 닿나요?

방문 순서가 예상과 다르면 정점 이름, 이웃의 순서, 방문 표시를 하는 시점을 차례로 확인해 보세요. 다음 장의 트리와 이진 트리의 구조에서는 사이클이 없는 연결 그래프인 트리를 다루고, 이 글의 두 탐색은 트리의 순회에서 다시 만납니다. 그래프 알고리즘을 더 깊이 공부하려면 MIT 6.006의 강의 노트를 참고하세요.