그래프 탐색: 너비 우선과 깊이 우선

지하철 노선도, 친구 관계, 웹 쪽의 링크, 미로는 모두 「점과 그 점들을 잇는 줄」입니다. 한 점에서 출발해 갈 수 있는 곳을 빠짐없이 들르는 방법이 두 가지 있습니다. 「다음」을 눌러 한 걸음씩 따라가 보세요.

한 줄 답. 너비 우선 탐색(BFS)은 가까운 정점(vertex)부터 물결처럼 퍼지며 들르고, 깊이 우선 탐색(DFS)은 한 길로 끝까지 들어갔다가 막히면 돌아 나옵니다. 두 코드의 차이는 한 줄입니다. 다음에 볼 정점을 큐(먼저 넣은 것부터)에서 꺼내면 너비 우선, 스택(나중에 넣은 것부터)에서 꺼내면 깊이 우선입니다. 둘 다 정점 수 + 간선(edge) 수에 비례하는 시간이 걸리고, 간선마다 길이가 같을 때 최단 경로(shortest path)는 너비 우선이 찾습니다.

주황은 지금 꺼낸 정점(「지금」 화살표), 초록은 이미 간 정점(검은 동그라미 숫자가 간 순서), 파란 점선은 큐나 스택에서 기다리는 정점, 회색은 아직 못 본 정점입니다. 굵은 초록 간선은 그 정점에 처음 들어온 간선이고, 걸음이 지나도 남습니다. 정점 하나를 「꺼냄 → 이웃을 살핌 → 넣음」 세 걸음으로 나눠 보여 줍니다. 살피는 걸음에서 굵은 파란 화살표 「넣음」은 아직 안 간 이웃이라 넣을 것, 흐린 회색 화살표 「이미 감」은 이미 간 이웃이라 넣지 않을 것입니다. 그림 아래쪽 칸 줄이 큐나 스택이고, 주황 칸이 다음에 나올 것입니다. 큐는 오른쪽(뒤)으로 들어가 왼쪽(앞)으로 나오고, 스택은 오른쪽 끝(위) 한쪽으로 들어가고 나옵니다. 그 걸음에 일어난 쪽의 화살표가 굵어집니다. 걸음 중간에 방법을 바꾸면 같은 걸음의 다른 방법을 볼 수 있습니다.

1. 그래프란: 정점과 간선

그래프는 정점(점)과 정점 둘을 잇는 간선으로 이루어집니다. 지하철역과 역 사이 선로, 사람과 친구 관계, 웹 쪽과 링크가 모두 그래프입니다. 간선으로 바로 이어진 두 정점을 서로의 이웃(인접한 정점)이라고 부릅니다.

위 실험의 그래프는 정점 9개(A ~ I), 간선 10개입니다. 간선에 방향이 없어서 A–B 간선으로 A 에서 B 로도, B 에서 A 로도 갑니다. 간선을 따라가다 처음 정점으로 돌아오는 사이클(cycle)도 있습니다(B → D → G → E → B). 사이클이 있어서 탐색은 「이미 간 곳」을 기억해야 합니다(5절).

2. 담는 법: 인접 리스트

컴퓨터에 그래프를 담는 가장 흔한 방법은 인접 리스트(adjacency list)입니다. 정점마다 이웃의 목록을 하나씩 둡니다. Python 이라면 dict 하나면 됩니다.

graph = {"A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"],
         "D": ["B", "G"], "E": ["B", "G", "H"], "F": ["C", "H"],
         "G": ["D", "E"], "H": ["E", "F", "I"], "I": ["H"]}

간선 하나(A–B)는 A 의 목록에 B 로, B 의 목록에 A 로 두 번 적힙니다. 그래서 목록의 길이를 모두 더하면 간선 수의 두 배, 여기서는 20 입니다. 이 쪽은 이웃을 이름 차례로 적었습니다. 목록의 차례가 바뀌면 들르는 순서도 바뀝니다. 모든 정점 쌍마다 칸을 하나씩 두는 표(인접 행렬)도 있지만, 정점이 V 개면 칸이 V × V 개라 간선이 적은 그래프에서는 대부분 빈칸입니다.

3. 차이는 하나: 다음 것을 어디서 꺼내나

두 방법 모두 「할 일 목록」 하나를 들고 같은 일을 되풀이합니다.

  1. 출발 정점을 할 일 목록에 넣는다.
  2. 목록에서 정점 하나를 꺼낸다.
  3. 이미 간 정점이면 버리고 2 로 돌아간다.
  4. 처음 온 정점이면 「갔다」고 표시하고, 아직 안 간 이웃을 모두 목록에 넣는다.
  5. 목록이 빌 때까지 2 ~ 4 를 되풀이한다.

다른 곳은 2 하나입니다.

B C 꺼냄 넣음 앞 뒤
큐: 뒤(오른쪽)로 넣고 앞(왼쪽)에서 꺼냅니다. B, C 를 차례로 넣으면 먼저 넣은 B 가 먼저 나옵니다.
B C 넣음 꺼냄 아래 위
스택: 위(오른쪽)로 넣고 같은 위에서 꺼냅니다. B, C 를 차례로 넣으면 나중에 넣은 C 가 먼저 나옵니다.

해 볼 것. ① 너비 우선으로 「다음」을 눌러 가면 간 순서가 A, B, C, D, E, F, G, H, I 입니다. 출발점에서 간선 1 개 거리인 B, C 를 다 본 뒤 2 개 거리인 D, E, F 로, 그다음 G, H, 마지막에 I 로 갑니다. ② 같은 걸음에서 깊이 우선으로 바꾸면 순서는 A, C, F, H, I, E, G, D, B 입니다. 스택은 나중에 넣은 C 를 먼저 꺼내므로 C 쪽으로 끝까지 들어갑니다. B 는 맨 처음에 넣었는데 맨 마지막에 갑니다. ③ 너비 우선의 걸음 21 에서는 G 를, 걸음 25 에서는 H 를 꺼내자마자 버립니다. 이웃 둘이 같은 정점을 한 번씩 넣었기 때문입니다. ④ 큐는 가장 길 때 4 칸(걸음 15, 18), 스택은 3 칸입니다. ⑤ 너비 우선의 굵은 초록 간선을 따라가면 출발점에서 각 정점까지 간선 수가 가장 적은 길입니다. 깊이 우선의 굵은 간선은 그렇지 않습니다(A 에서 B 까지 간선 7 개를 돌아갑니다).

4. 손으로 따라가기

위 실험과 같은 그래프를 A 에서 출발해 끝까지 따라갑니다. 한 줄이 정점 하나를 꺼내는 일입니다(위 실험은 이것을 「꺼냄 → 이웃을 살핌 → 넣음」, 많아야 세 걸음으로 나눠 보여 줍니다). 동그라미 숫자는 간 순서이고, 「꺼낸 뒤」 칸은 이웃까지 넣은 뒤의 모습입니다. 큐는 왼쪽이 앞(다음에 나올 것), 스택은 오른쪽이 위(다음에 나올 것)입니다. 마지막 칸은 그 정점이 나온 까닭입니다.

꺼내기너비 우선: 꺼낸 정점꺼낸 뒤 큐깊이 우선: 꺼낸 정점꺼낸 뒤 스택왜 그 정점인가
0(A 를 넣음)A(A 를 넣음)A출발 정점을 넣고 시작
1A ①B CA ①B C둘 다 A 하나뿐
2B ②C D EC ②B F큐 맨 앞 B(먼저 넣음) · 스택 맨 위 C(나중에 넣음)
3C ③D E FF ③B H큐 맨 앞 C · 스택 맨 위 F(방금 넣음)
4D ④E F GH ④B E I큐 맨 앞 D · 스택 맨 위 H(방금 넣음)
5E ⑤F G G HI ⑤B E큐 맨 앞 E · 스택 맨 위 I(E 다음에 넣음)
6F ⑥G G H HE ⑥B B G큐 맨 앞 F · 스택 맨 위 E(I 가 나가 드러남)
7G ⑦G H HG ⑦B B D큐 맨 앞 G · 스택 맨 위 G(방금 넣음)
8G 버림H HD ⑧B B B큐의 G 는 ⑦에서 이미 감 · 스택 맨 위 D(방금 넣음)
9H ⑧H IB ⑨B B큐 맨 앞 H · 스택 맨 위 B(D 가 넣음)
10H 버림IB 버림B큐의 H 는 ⑧에서 이미 감 · 스택의 B 는 ⑨에서 이미 감
11I ⑨(빔)B 버림(빔)큐 맨 앞 I · 스택의 B 는 ⑨에서 이미 감

깊이 우선의 꺼내기 4 를 보세요. H 를 꺼내 이웃 E, I 를 넣으면, 나중에 넣은 I 가 맨 위에 있어 바로 다음에 나옵니다. 너비 우선이었다면 I 는 큐의 맨 뒤에 서서 G, H 보다 늦게 나옵니다.

5. 방문 표시를 안 하면 끝없이 돈다

3절의 「이미 간 정점이면 버린다」를 빼 봅니다. A 를 꺼내 B 를 넣고, B 를 꺼내면 이웃 A 를 다시 넣고, A 를 꺼내면 또 B 를 넣습니다. 간선 하나를 사이에 두고 끝없이 오가고, 할 일 목록은 비지 않습니다. 사이클(B → D → G → E → B)이 있으면 사이클을 돌고 또 돕니다. 그래서 「갔다」는 표시를 둡니다. Python 이라면 set 하나, 정점에 번호를 붙였다면 정점 수만큼의 참·거짓 배열입니다.

이 쪽은 두 방법 모두 꺼낼 때 표시합니다. 그래야 두 코드가 꺼내는 줄 하나만 다릅니다. 그 대신 같은 정점이 목록에 두 번 들어가기도 합니다(4절 꺼내기 5 의 G G). 너비 우선은 넣을 때 표시해도 간 순서가 같고 큐에 같은 정점이 두 번 들어가지 않아서, 흔히 그렇게 짭니다.

6. 미로에서: 최단 경로

격자 미로도 그래프입니다. 칸 하나가 정점이고, 위·아래·왼쪽·오른쪽으로 붙은 빈칸이 이웃입니다. 출발(왼쪽 위)에서 시작해 도착(오른쪽 아래)을 꺼내면 멈춥니다. 칸마다 「어느 칸에서 들어왔나」를 적어 두었다가, 도착에서 거꾸로 따라가면 찾은 길이 나옵니다.

칸 가운데 큰 숫자는 찾은 길을 따라 출발에서 몇 칸 왔는지, 오른쪽 아래 작은 숫자는 몇 번째로 들른 칸인지입니다. 초록은 들른 칸, 파란 점선은 기다리는 칸, 주황 테두리는 지금 꺼낸 칸, 짙은 칸은 벽입니다. 파란 화살표는 지금 칸에서 할 일 목록에 넣은 이웃 칸을 가리킵니다. 「다음」은 새 칸 하나를 들를 때까지 나아갑니다(이미 간 칸을 꺼내 버리는 걸음은 건너뜁니다). 이웃은 위, 오른쪽, 아래, 왼쪽 차례로 넣습니다. 벽은 고정 씨앗 난수기로 지어낸 것이라 쪽을 열 때마다 같습니다.

해 볼 것. ① 너비 우선으로 「다음」을 눌러 가면 숫자가 1, 2, 3 … 으로 물결처럼 번집니다. 같은 숫자의 칸을 다 들른 뒤에 다음 숫자로 넘어갑니다. ② 「끝까지」를 누르면 길이 14, 들른 칸 47 개입니다. 14 는 오른쪽 7 칸과 아래 7 칸을 더한 것이라 이 격자에서 더 짧은 길은 없습니다. ③ 깊이 우선으로 바꿔 「끝까지」를 누르면 길이 28, 들른 칸 30 개입니다. 들른 칸은 적지만 길은 두 배입니다. 깊이 우선은 처음 닿은 길을 그대로 내놓고, 그 길이 가장 짧은지는 보지 않습니다. ④ 셋째 줄 둘째 칸을 보세요. 깊이 우선이 끝났을 때는 17, 너비 우선이 끝났을 때는 3 입니다. 깊이 우선의 숫자는 가장 짧은 거리가 아니라 「돌아 들어온 길의 길이」입니다.

7. 걸리는 시간

걸리는 시간 ∝ V + E          (책의 표기: O(V + E))

목록에 넣는 횟수도 간선마다 많아야 두 번(양쪽 끝에서 한 번씩)이라, 꺼내는 횟수까지 합해도 V + E 에 비례합니다. 위 그래프(V = 9, E = 10)에서는 두 방법 모두 넣기 11 번, 꺼내기 11 번입니다. 인접 리스트 대신 V × V 표에 담으면 정점마다 표의 한 줄 V 칸을 다 봐야 해서 V × V 에 비례합니다.

8. 언제 무엇을 쓰나

방법걸리는 시간(가장 좋을 때 · 보통 · 가장 나쁠 때)더 드는 메모리좋은 점나쁜 점쓰는 경우
너비 우선(큐)찾는 정점이 출발점 바로 옆이면 몇 걸음 · 다 훑으면 V + E · V + E(정점과 간선이 두 배면 두 배)방문 표시 V 칸 + 큐. 출발점에서 같은 거리인 정점이 한꺼번에 큐에 들어가, 옆으로 넓은 그래프일수록 큐가 길다지나는 간선 수가 가장 적은 길을 찾는다. 가까운 것부터 본다멀리 있는 것을 찾을 때도 가까운 것을 먼저 다 본다간선마다 길이가 같을 때 최단 경로(미로, 몇 다리 건너인가)
깊이 우선(스택 또는 재귀)같다방문 표시 V 칸 + 스택. 스택에는 지금 들어가 있는 길과 그 옆에 남겨 둔 갈림길이 쌓인다짧게 짤 수 있고(재귀 몇 줄), 한 길을 끝까지 따라가는 성질이 사이클 찾기와 위상 정렬에 맞다찾은 길이 가장 짧다는 보장이 없다. 재귀로 짜면 아주 긴 길에서 호출이 너무 깊어질 수 있다끝까지 가 보기(이어져 있나, 연결 요소 나누기), 사이클 찾기, 위상 정렬

이 쪽처럼 꺼낼 때 표시하면 같은 정점이 여러 번 들어가 큐와 스택이 간선 수에 비례해 길어질 수 있습니다. 간선마다 길이(시간, 거리, 요금)가 다르면 간선 수가 적은 길이 더 멀 수 있습니다. 그때는 너비 우선 대신 다익스트라 알고리즘을 씁니다.

9. Python 으로

from collections import deque

def search(graph, start, wide=True):
    todo, visited, order = deque([start]), set(), []
    while todo:
        node = todo.popleft() if wide else todo.pop()   # 큐는 앞에서, 스택은 뒤에서
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        todo.extend(n for n in graph[node] if n not in visited)
    return order

print(search(graph, "A"))              # ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
print(search(graph, "A", wide=False))  # ['A', 'C', 'F', 'H', 'I', 'E', 'G', 'D', 'B']

graph 는 2절의 dict 입니다. collections.deque 는 양쪽 끝에서 넣고 빼는 것이 빠른 목록입니다. popleft() 는 앞에서(큐), pop() 은 뒤에서(스택) 꺼냅니다. 보통 list 로 큐를 만들어 pop(0) 을 쓰면 뒤의 값을 모두 한 칸씩 당겨야 해서, 목록이 길수록 느려집니다.

어디에 쓰나

자주 묻는 것

너비 우선과 깊이 우선은 들르는 정점이 다른가요?

아닙니다. 출발 정점에서 간선을 따라 갈 수 있는 정점은 두 방법 모두 빠짐없이 한 번씩 들릅니다. 다른 것은 들르는 순서뿐입니다. 출발 정점에서 닿지 않는 정점은 둘 다 들르지 않습니다.

깊이 우선은 재귀로 짜야 하나요?

아닙니다. 함수가 자기를 부르는 재귀는 컴퓨터가 쌓아 두는 호출 스택을 쓰는 것이라, 스택을 직접 써도 깊이 우선이 됩니다. 이 쪽의 실험과 Python 코드가 스택을 직접 씁니다. 재귀로 짜면 인접 리스트의 앞쪽부터, 스택에 넣어 꺼내면 뒤쪽부터 들어가 순서가 다를 수 있지만 둘 다 깊이 우선입니다.

최단 경로는 늘 너비 우선으로 찾나요?

간선마다 길이가 같을 때만 그렇습니다. 너비 우선은 지나는 간선의 수가 가장 적은 길을 찾습니다. 간선마다 길이나 비용이 다르면 간선 수가 적은 길이 더 멀 수 있어 다익스트라 알고리즘을 씁니다.

낱말

여기서 쓴 말책에서 부르는 말
점정점(vertex), 노드(node)
점을 잇는 줄간선(edge)
이웃인접한 정점(adjacent vertex)
정점마다 이웃을 적은 목록인접 리스트(adjacency list)
모든 정점 쌍의 표인접 행렬(adjacency matrix)
너비 우선너비 우선 탐색(breadth-first search, BFS)
깊이 우선깊이 우선 탐색(depth-first search, DFS)
먼저 넣은 것부터 꺼내는 목록큐(queue), 선입선출(FIFO)
나중에 넣은 것부터 꺼내는 목록스택(stack), 후입선출(LIFO)
양쪽 끝에서 넣고 빼는 목록덱(deque, double-ended queue)
처음 정점으로 돌아오는 길순환, 사이클(cycle)
간 곳 표시방문 표시(visited, marked)
이어진 한 덩어리연결 요소(connected component)
차례 정하기위상 정렬(topological sort)
가장 짧은 길최단 경로(shortest path)

출처

← 레드블랙 트리위상 정렬 →