그래프 탐색: 너비 우선과 깊이 우선
지하철 노선도, 친구 관계, 웹 쪽의 링크, 미로는 모두 「점과 그 점들을 잇는 줄」입니다. 한 점에서 출발해 갈 수 있는 곳을 빠짐없이 들르는 방법이 두 가지 있습니다. 「다음」을 눌러 한 걸음씩 따라가 보세요.
한 줄 답. 너비 우선 탐색(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. 차이는 하나: 다음 것을 어디서 꺼내나
두 방법 모두 「할 일 목록」 하나를 들고 같은 일을 되풀이합니다.
- 출발 정점을 할 일 목록에 넣는다.
- 목록에서 정점 하나를 꺼낸다.
- 이미 간 정점이면 버리고 2 로 돌아간다.
- 처음 온 정점이면 「갔다」고 표시하고, 아직 안 간 이웃을 모두 목록에 넣는다.
- 목록이 빌 때까지 2 ~ 4 를 되풀이한다.
다른 곳은 2 하나입니다.
- 너비 우선: 큐. 먼저 넣은 것부터 꺼냅니다(줄 서기). 출발점에서 간선 1 개 거리인 정점을 다 본 뒤에야 2 개 거리로 넘어갑니다. 그래서 물결처럼 퍼집니다.
- 깊이 우선: 스택. 나중에 넣은 것부터 꺼냅니다(접시 쌓기). 방금 넣은 이웃으로 바로 들어가고, 더 갈 곳이 없을 때에야 아까 넣어 둔 갈림길로 돌아옵니다.
해 볼 것. ① 너비 우선으로 「다음」을 눌러 가면 간 순서가 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 | 출발 정점을 넣고 시작 |
| 1 | A ① | B C | A ① | B C | 둘 다 A 하나뿐 |
| 2 | B ② | C D E | C ② | B F | 큐 맨 앞 B(먼저 넣음) · 스택 맨 위 C(나중에 넣음) |
| 3 | C ③ | D E F | F ③ | B H | 큐 맨 앞 C · 스택 맨 위 F(방금 넣음) |
| 4 | D ④ | E F G | H ④ | B E I | 큐 맨 앞 D · 스택 맨 위 H(방금 넣음) |
| 5 | E ⑤ | F G G H | I ⑤ | B E | 큐 맨 앞 E · 스택 맨 위 I(E 다음에 넣음) |
| 6 | F ⑥ | G G H H | E ⑥ | B B G | 큐 맨 앞 F · 스택 맨 위 E(I 가 나가 드러남) |
| 7 | G ⑦ | G H H | G ⑦ | B B D | 큐 맨 앞 G · 스택 맨 위 G(방금 넣음) |
| 8 | G 버림 | H H | D ⑧ | B B B | 큐의 G 는 ⑦에서 이미 감 · 스택 맨 위 D(방금 넣음) |
| 9 | H ⑧ | H I | B ⑨ | B B | 큐 맨 앞 H · 스택 맨 위 B(D 가 넣음) |
| 10 | H 버림 | I | B 버림 | B | 큐의 H 는 ⑧에서 이미 감 · 스택의 B 는 ⑨에서 이미 감 |
| 11 | I ⑨ | (빔) | 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: 간선의 수. 인접 리스트의 길이를 다 더하면 2E 라서, 이웃을 보는 일이 모두 합해 2E 번입니다.∝: 비례한다. 정점과 간선이 모두 두 배면 시간도 두 배쯤입니다.O( ): 입력이 커질 때 시간이 자라는 빠르기만 적는 표기(시간 복잡도).
목록에 넣는 횟수도 간선마다 많아야 두 번(양쪽 끝에서 한 번씩)이라, 꺼내는 횟수까지 합해도 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) 을 쓰면 뒤의 값을 모두 한 칸씩 당겨야 해서, 목록이 길수록 느려집니다.
어디에 쓰나
- 미로와 게임 격자의 길 찾기. 한 칸 옮기는 데 드는 것이 모두 같으면 너비 우선이 최단 경로를 찾습니다.
- 몇 다리 건너인가. 사람 관계 그래프에서 너비 우선으로 두 사람 사이의 간선 수를 잽니다.
- 이어져 있나, 연결 요소 나누기. 한 정점에서 훑어 닿는 정점들이 한 연결 요소(connected component)입니다. 닿지 않은 정점에서 다시 훑으면 다음 연결 요소가 나옵니다. 어느 방법을 써도 됩니다.
- 사이클 찾기. 방향 없는 그래프에서 훑는 중에, 바로 전 정점이 아닌 이미 간 정점으로 이어진 간선을 만나면 사이클이 있습니다.
- 위상 정렬(topological sort). 「A 를 끝내야 B 를 한다」 같은 방향 있는 간선으로 일을 이은 그래프에서, 깊이 우선으로 정점을 다 끝낸 순서를 거꾸로 읽으면 해도 되는 차례가 나옵니다(빌드 순서, 과목 수강 순서). 사이클이 있으면 그런 차례는 없습니다.
자주 묻는 것
너비 우선과 깊이 우선은 들르는 정점이 다른가요?
아닙니다. 출발 정점에서 간선을 따라 갈 수 있는 정점은 두 방법 모두 빠짐없이 한 번씩 들릅니다. 다른 것은 들르는 순서뿐입니다. 출발 정점에서 닿지 않는 정점은 둘 다 들르지 않습니다.
깊이 우선은 재귀로 짜야 하나요?
아닙니다. 함수가 자기를 부르는 재귀는 컴퓨터가 쌓아 두는 호출 스택을 쓰는 것이라, 스택을 직접 써도 깊이 우선이 됩니다. 이 쪽의 실험과 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) |
출처
- Robert Sedgewick, Kevin Wayne, Algorithms, 4th ed., 4.1 Undirected Graphs. 그래프와 이웃 목록, 깊이 우선과 너비 우선, 걸리는 시간 V + E, 너비 우선의 가장 짧은 길.
- Python 문서: collections.deque. 양쪽 끝의 append·pop, list 의 pop(0) 이 느린 까닭.