최소 신장 트리: 크루스칼과 프림
마을 일곱 곳을 전선으로 모두 이어야 합니다. 깔 수 있는 자리마다 공사비가 다릅니다. 어느 자리를 골라야 가장 싸게 모두 이어질까요? 두 가지 방법을 한 걸음씩 따라가 보세요.
한 줄 답. 최소 신장 트리는 모든 정점(vertex)을 사이클(cycle) 없이 잇는 간선(edge) 묶음 가운데 값의 합이 가장 작은 것입니다. 간선은 늘 정점 수 − 1 개입니다. 크루스칼은 값이 작은 간선부터 보며 사이클이 생기는 간선만 버리고, 프림은 한 정점에서 시작해 지금까지 만든 트리 밖으로 나가는 가장 싼 간선을 하나씩 붙입니다. 두 방법은 같은 합에 닿습니다. 한 정점에서 가는 최단 경로(다익스트라)와는 다른 문제입니다.
위에서 방법을 고르고 「다음」을 누르세요. 초록 굵은 간선이 고른 간선, 흐린 점선과 값에 가로줄이 그어진 것이 버린 간선, 주황 띠와 주황 테두리가 이번 걸음에 본 간선입니다. 주황 화살표는 이번 걸음의 일입니다: 아래 간선 목록에서는 지금 보는 간선, 그래프에서는 고른 간선이 잇는 쪽(합쳐지는 연결 요소, 들어오는 정점)이고, 주황 점선은 사이클이 되는 길입니다. 크루스칼에서 정점 옆 작은 번호는 연결 요소(connected component) 번호로, 번호가 같으면 같은 연결 요소입니다. 프림에서는 연한 초록 영역이 트리, 그 테두리가 경계, 파란 점선이 경계를 건너는 간선(후보)입니다. 그래프와 값은 지어낸 것입니다.
1. 문제: 모든 정점을 가장 싸게 잇기
정점(점) 몇 개와, 두 정점을 잇는 간선이 있습니다. 간선마다 값, 곧 가중치(weight)가 붙어 있습니다. 마을과 마을 사이에 전선을 깔 수 있는 자리와 그 공사비를 떠올리면 됩니다. 할 일은 간선을 골라 모든 정점이 이어지게 하되, 고른 간선 가중치의 합이 가장 작게 하는 것입니다.
이렇게 고른 간선 묶음은 두 규칙을 지킵니다.
- 사이클이 없습니다. 사이클이 있으면 그 사이클의 간선 하나를 빼도 모두 이어져 있습니다. 값이 모두 양수라면 빼는 쪽이 쌉니다.
- 간선은 정점 수 − 1 개입니다. 정점 V 개를 사이클 없이 모두 이으면 간선은 꼭 V − 1 개가 됩니다. 실험은 정점 7개라 간선 6개입니다.
모든 정점을 사이클 없이 잇는 간선 묶음을 신장 트리라고 부르고, 그 가운데 합이 가장 작은 것을 최소 신장 트리라고 부릅니다. 재는 값은 이것 하나입니다.
W(T) = w(e₁) + w(e₂) + … + w(e_{V−1})
T: 고른 간선 묶음(신장 트리).e₁, e₂, …: T 에 든 간선. V − 1 개입니다.w(e): 간선 e 의 가중치.V: 정점 수.W(T): T 의 합. 이것이 가장 작은 T 를 찾습니다.
실험의 그래프는 정점 7개, 간선 12개이고, 최소 신장 트리의 합은 24 입니다.
2. 크루스칼: 싼 간선부터, 사이클은 버린다
- 간선을 값이 작은 순서로 늘어놓습니다.
- 하나씩 봅니다. 두 끝이 아직 다른 연결 요소면 고릅니다. 두 연결 요소가 하나가 됩니다.
- 두 끝이 이미 이어져 있으면 버립니다. 고르면 사이클이 생기기 때문입니다.
- 간선 V − 1 개를 고르면 멈춥니다.
처음에는 정점마다 따로인 연결 요소 7개가 있고, 간선을 하나 고를 때마다 연결 요소가 하나씩 줄어 마지막에 하나가 됩니다. 「두 끝이 이미 이어져 있나」를 빨리 묻는 방법은 5절에서 봅니다.
해 볼 것. 크루스칼로 「다음」을 누르면 간선마다 두 걸음씩 갑니다. 먼저 두 끝의 연결 요소 번호를 비교하고, 다음 걸음에 고르거나 버립니다. E–F 1, D–G 2, B–F 3, A–B 4, C–F 5 를 차례로 고릅니다. 여섯째로 본 B–C 6 은 B 와 C 가 이미 F 를 거쳐 이어져 있어 버리고, A–F 7 과 A–E 8 도 버립니다. C–D 9 를 고르면 간선이 6개가 되어 걸음 19 에서 끝납니다. 합은 1 + 2 + 3 + 4 + 5 + 9 = 24 입니다. F–G 10, C–G 11, E–G 12 는 보지도 않습니다.
3. 프림: 트리를 한 정점씩 키운다
- 아무 정점 하나로 연결 요소를 시작합니다. 실험은 A 에서 시작합니다.
- 연결 요소 안의 정점과 밖의 정점을 잇는 간선 가운데 가장 싼 것을 고르고, 밖에 있던 정점을 연결 요소에 넣습니다.
- 두 끝이 모두 연결 요소 안이 된 간선은 다시 쓸 일이 없으니 버립니다.
- 모든 정점이 들어오면(간선 V − 1 개) 멈춥니다.
해 볼 것. 프림으로 바꾸면 정점마다 두 걸음씩(경계를 건너는 간선을 비교하고, 가장 싼 것을 고름) 가며 A–B 4, B–F 3, E–F 1, C–F 5, C–D 9, D–G 2 를 차례로 고르고, 걸음 13 에서 합 24 로 끝납니다. 고른 간선 여섯은 크루스칼과 같고 차례만 다릅니다. 값 1 인 E–F 를 크루스칼은 맨 먼저, 프림은 셋째로 고릅니다. 트리가 F 에 닿기 전에는 E–F 가 연결 요소 밖으로 나가는 간선이 아니기 때문입니다.
두 방법이 같은 답을 내는지는 이 쪽의 자가 검사(주소 끝에 ?test)가 확인합니다. 두 방법의 합이 모두 24 이고 고른 간선이 같은지, 프림을 일곱 정점 어디에서 시작해도 24 인지, 간선 12개에서 6개를 고르는 924 가지를 모두 해 봐도 신장 트리 가운데 가장 싼 합이 24 인지 봅니다.
4. 손으로 따라가기
실험과 같은 그래프입니다. 크루스칼은 값 순서로 간선을 봅니다.
| 차례 | 간선 | 값 | 두 끝이 이미 이어져 있나 | 한 일 | 합 |
|---|---|---|---|---|---|
| 1 | E–F | 1 | 아니오 | 고름 | 1 |
| 2 | D–G | 2 | 아니오 | 고름 | 3 |
| 3 | B–F | 3 | 아니오 | 고름 | 6 |
| 4 | A–B | 4 | 아니오 | 고름 | 10 |
| 5 | C–F | 5 | 아니오 | 고름 | 15 |
| 6 | B–C | 6 | 예(B–F–C) | 버림 | 15 |
| 7 | A–F | 7 | 예(A–B–F) | 버림 | 15 |
| 8 | A–E | 8 | 예(A–B–F–E) | 버림 | 15 |
| 9 | C–D | 9 | 아니오 | 고름. 간선 6개라 끝 | 24 |
프림은 A 에서 시작해 트리 밖으로 나가는 간선만 봅니다.
| 차례 | 연결 요소 | 밖으로 나가는 간선(값) | 고른 간선(그 가운데 가장 싼 것) | 합 |
|---|---|---|---|---|
| 1 | A | A–B 4, A–F 7, A–E 8 | A–B | 4 |
| 2 | A, B | B–F 3, B–C 6, A–F 7, A–E 8 | B–F | 7 |
| 3 | A, B, F | E–F 1, C–F 5, B–C 6, A–E 8, F–G 10 | E–F | 8 |
| 4 | A, B, F, E | C–F 5, B–C 6, F–G 10, E–G 12 | C–F | 13 |
| 5 | A, B, F, E, C | C–D 9, F–G 10, C–G 11, E–G 12 | C–D | 22 |
| 6 | A, B, F, E, C, D | D–G 2, F–G 10, C–G 11, E–G 12 | D–G | 24 |
5. 「이미 이어져 있나」를 빨리 묻기: 유니온 파인드
크루스칼은 간선마다 「두 끝이 이미 이어져 있나」를 묻습니다. 물을 때마다 고른 간선을 따라 길을 찾으면 그래프를 다시 훑어야 합니다. 유니온 파인드는 이 물음에 빨리 답하는 작은 자료 구조입니다.
- 칸 하나씩. 정점마다 「가리키는 정점」을 적는 칸이 있습니다. 처음에는 저마다 자기 자신을 가리킵니다.
- 같은 연결 요소인가(find). 가리키는 칸을 따라 자기 자신을 가리키는 정점까지 올라갑니다. 그 정점이 연결 요소의 루트(root, 대표)입니다. 두 정점의 루트가 같으면 같은 연결 요소입니다.
- 잇기(union). 두 정점의 루트를 찾아 한 루트가 다른 루트를 가리키게 합니다. 이때 정점이 적은 트리를 많은 트리 밑에 붙입니다. 그러면 어느 정점도 루트까지 lg n 걸음보다 멀지 않습니다. n 은 정점 수, lg 는 2 를 몇 번 곱해야 n 이 되나입니다.
정점 둘을 고르고 「잇기」나 「같은 연결 요소인가」를 누르세요. 화살표는 그 정점의 칸이 가리키는 정점입니다. 방금 루트까지 따라 올라간 길과 그 칸이 주황으로 칠해집니다. 그림은 아래 표의 칸을 트리로 그린 것입니다.
해 볼 것. 크루스칼이 고른 차례대로 E–F, D–G, B–F, A–B, C–F 를 「잇기」 하세요. 그다음 B 와 C 로 「같은 연결 요소인가」를 누르면 B → E, C → E 로 루트가 둘 다 E 입니다. 크루스칼이 B–C 를 버린 까닭이 이것입니다. 이어서 C 와 D 를 「잇기」 하면 루트 D 의 트리(정점 2개)가 루트 E 의 트리(정점 5개) 밑에 붙습니다. 이제 G 를 고르면 G → D → E 로 두 걸음 올라갑니다. 정점 7개를 모두 이어도 루트까지 가장 먼 정점이 두 걸음입니다(lg 7 은 약 2.8).
경로 압축(path compression). 올라가며 지난 정점들이 루트를 바로 가리키게 고쳐 두면 다음 물음이 더 짧아집니다. 작은 트리를 밑에 붙이기와 경로 압축을 함께 쓰면, 한 번 묻는 데 드는 일이 평균으로 거의 일정합니다. 출처는 이 값이 실제로 나올 수 있는 어떤 n 에서도 5 보다 작은 함수(역 아커만 함수)로 묶인다고 적습니다. 위 실험은 올라가는 길이 잘 보이도록 경로 압축을 하지 않습니다.
크루스칼을 파이썬으로 짧게 쓰면 이렇습니다. 작게 줄이느라 트리 크기 비교와 경로 압축은 뺐습니다.
def kruskal(n, edges): # edges: [(값, u, v), ...], 정점은 0 ~ n−1
parent = list(range(n)) # 처음엔 저마다 자기가 루트
def find(x): # 가리키는 칸을 따라 루트까지 올라간다
while parent[x] != x:
x = parent[x]
return x
tree = []
for w, u, v in sorted(edges): # 값이 작은 간선부터
ru, rv = find(u), find(v)
if ru != rv: # 다른 연결 요소일 때만 고른다
parent[rv] = ru # 잇기
tree.append((w, u, v))
return tree
프림은 후보 간선을 힙에 넣고 가장 싼 것을 꺼냅니다. 파이썬에서는 w, u, v = heapq.heappop(candidates) 한 줄입니다.
6. 왜 「가장 싼 간선부터」가 맞나: 컷 성질(cut property)
정점들을 아무렇게나 두 무리로 갈라(컷, cut) 봅니다. 한 무리의 정점과 다른 무리의 정점을 잇는 간선을 교차 간선(crossing edge)이라고 부릅니다. 출처의 성질은 이렇습니다: 교차 간선 가운데 가장 싼 것은 반드시 최소 신장 트리에 들어 있습니다(가중치가 모두 다를 때). 두 무리는 결국 어느 간선으로든 이어져야 하고, 그 간선은 가장 싼 교차 간선이라는 뜻입니다.
- 프림은 이 성질을 그대로 씁니다. 「트리」와 「나머지」로 가르고, 그 경계를 건너는 가장 싼 간선을 고릅니다.
- 크루스칼이 간선 u–v 를 고르는 순간, u 가 든 연결 요소와 나머지로 갈라 봅니다. u–v 보다 싼 간선은 이미 다 봤고, 고른 것이든 버린 것이든 두 끝이 한 연결 요소 안에 있어 이 경계를 건너지 않습니다. 그래서 u–v 가 교차 간선 가운데 가장 쌉니다.
매 걸음 지금 가장 좋아 보이는 것을 고르고 되돌리지 않는 방식을 탐욕 알고리즘이라고 부릅니다. 출처는 두 방법을 모두 탐욕 알고리즘의 한 경우로 설명합니다. 탐욕이 늘 맞는 답을 내지는 않는데, 이 문제에서는 컷 성질이 맞는다는 것을 보장합니다.
7. 꼭 알아야 할 성질
| 성질 | 쉬운 말 | 실험에서 |
|---|---|---|
| 간선은 V − 1 개, 사이클 없음 | 정점 V 개를 사이클 없이 모두 이으면 간선은 꼭 V − 1 개 | 정점 7개, 고른 간선 6개 |
| 값이 모두 다르면 하나뿐 | 최소 신장 트리가 하나라서 어느 방법으로 구해도 같은 간선이 나온다 | 크루스칼과 프림이 같은 6개를 고른다 |
| 값이 0 이나 음수여도 된다 | 값은 거리가 아니어도 된다. 크루스칼과 프림은 그대로 돈다 | 자가 검사: 모든 값에서 5 를 빼도 같은 간선, 합 −6 |
| 최단 경로와 다르다 | 트리 위의 두 정점 사이 길이 최단 경로는 아닐 수 있다 | D 에서 F: 트리 위 14, 최단 경로 12 |
| 그래프가 이어져 있어야 한다 | 끊긴 그래프에는 신장 트리가 없다. 조각마다 따로 구한다 | 자주 묻는 것 3 |
8. 언제 무엇을 쓰나
걸리는 시간은 출처의 「가장 나쁠 때」입니다. 출처는 가장 좋을 때와 보통은 따로 적지 않습니다.
| 방법 | 걸리는 시간(가장 나쁠 때) | 더 드는 메모리 | 좋은 점 | 나쁜 점 | 쓰는 경우 |
|---|---|---|---|---|---|
| 크루스칼 | E log E. 간선이 두 배면 두 배보다 조금 더 | 간선 수 E 에 비례 | 간선 목록만 있으면 된다. 정렬과 유니온 파인드로 짧게 짠다 | 간선 전체를 값 순서로 다뤄야 한다 | 간선이 적을 때, 자료가 간선 목록으로 올 때 |
| 프림(게으른 판) | E log E | E 에 비례 | 우선순위 큐 하나로 트리를 키운다 | 안쪽이 된 간선도 큐에 남겨 두었다가 꺼낼 때 버린다 | 짜기 쉬운 프림이 필요할 때 |
| 프림(서두르는 판) | E log V | 정점 수 V 에 비례 | 밖의 정점마다 트리로 오는 가장 싼 간선 하나만 큐에 둔다 | 값을 줄일 수 있는 우선순위 큐가 필요하다 | 간선이 적거나 보통일 때 |
| 프림(배열 판) | V². 정점이 두 배면 네 배 | V 에 비례 | 큐 없이 배열을 훑어 가장 가까운 정점을 찾는다 | 간선이 적어도 V² 이 든다 | 간선이 아주 많을 때. 출처는 빽빽한 그래프에 가장 알맞다고 적는다 |
V: 정점 수.E: 간선 수.log: 2 를 몇 번 곱해야 그 수가 되나. 수가 두 배가 되어도 1 만 커진다.E log E: 간선 E 개를 값 순서로 다루는 데 드는 일. 간선을 정렬하는 것과 같은 크기다(시간 복잡도).
간선이 적을 때(E 가 V 와 비슷할 때) 크루스칼의 E log E 와 서두르는 프림의 E log V 는 거의 같습니다. 짜기 쉬운 쪽을 고르면 됩니다. 간선이 많을 때(정점마다 거의 모든 정점과 이어져 E 가 V² 에 가까울 때) E log E 는 V² × log 쯤으로 커져 배열 판 프림의 V² 보다 큽니다.
어디에 쓰나
- 배선과 관 깔기. 여러 지점을 전선, 관, 도로로 모두 이을 때 공사비 합이 가장 작은 배치를 찾습니다.
- 통신망 깔기. 여러 곳을 회선으로 모두 이을 때 회선 비용이 가장 적게 드는 연결을 고릅니다.
자주 묻는 것
다익스트라의 최단 경로와 무엇이 다른가요?
다익스트라는 한 정점에서 다른 정점들까지 가는 최단 경로를 찾습니다. 최소 신장 트리는 모든 정점을 잇는 간선 묶음의 합을 가장 작게 합니다. 그래서 트리 위의 길이 최단 경로라는 보장은 없습니다. 실험의 그래프에서 D 에서 F 로 가는 트리 위의 길은 D–C–F 로 9 + 5 = 14 이지만, 최단 경로는 D–G–F 로 2 + 10 = 12 입니다.
값이 같은 간선이 있으면 어떻게 되나요?
두 방법 모두 그대로 돕니다. 다만 최소 신장 트리가 여럿일 수 있어서, 같은 값 가운데 어느 간선을 먼저 보느냐에 따라 고른 간선이 달라질 수 있습니다. 어느 쪽이든 합은 가장 작은 값으로 같습니다.
그래프가 두 조각으로 끊겨 있으면요?
모든 정점을 잇는 트리가 없습니다. 이때는 조각마다 최소 신장 트리를 구하고, 이것들을 모아 최소 신장 숲이라고 부릅니다. 크루스칼은 간선을 끝까지 보면 조각마다의 트리를 한꺼번에 내고, 프림은 조각마다 따로 시작해야 합니다.
낱말
| 여기서 쓴 말 | 책에서 부르는 말 |
|---|---|
| 점 | 정점, 꼭짓점(vertex) |
| 점을 잇는 줄 | 간선(edge) |
| 간선의 값 | 가중치(weight). 값이 붙은 그래프는 가중 그래프(edge-weighted graph) |
| 처음 정점으로 돌아오는 길 | 사이클(cycle) |
| 모든 정점을 사이클 없이 잇는 간선 묶음 | 신장 트리(spanning tree) |
| 합이 가장 작은 신장 트리 | 최소 신장 트리(minimum spanning tree, MST) |
| 이어진 한 연결 요소 | 연결 요소(connected component) |
| 두 무리로 가르기, 건너는 간선 | 컷(cut), 교차 간선(crossing edge) |
| 자르는 성질 | 컷 성질(cut property) |
| 지금 가장 좋아 보이는 것을 고르는 방식 | 탐욕 알고리즘(greedy algorithm) |
| 「이미 이어져 있나」를 묻는 자료 구조 | 유니온 파인드(union-find) |
| 대표 | 루트(root) |
| 작은 트리를 큰 트리 밑에 붙이기 | 가중 퀵 유니온(weighted quick-union) |
| 길 줄이기 | 경로 압축(path compression) |
| 가장 싼 것을 꺼내는 큐 | 우선순위 큐(priority queue) |
| 끊긴 그래프의 조각마다의 트리 | 최소 신장 숲(minimum spanning forest) |
출처
- Robert Sedgewick, Kevin Wayne, Algorithms, 4.3 Minimum Spanning Trees. 정의와 가정(이어진 그래프, 값이 0 이나 음수여도 됨, 값이 같으면 하나가 아닐 수 있음, 최소 신장 숲), 컷 성질과 탐욕 알고리즘, 크루스칼과 프림(게으른 판, 서두르는 판)의 절차, 걸리는 시간과 메모리, 배열 판 프림의 V².
- Robert Sedgewick, Kevin Wayne, Algorithms, 1.5 Case Study: Union-Find. 대표까지 따라 올라가기(quick-union), 작은 나무를 큰 나무 밑에 붙이기와 깊이 lg n, 길 줄이기와 역 아커만 함수.