최소 신장 트리: 크루스칼과 프림

마을 일곱 곳을 전선으로 모두 이어야 합니다. 깔 수 있는 자리마다 공사비가 다릅니다. 어느 자리를 골라야 가장 싸게 모두 이어질까요? 두 가지 방법을 한 걸음씩 따라가 보세요.

한 줄 답. 최소 신장 트리는 모든 정점(vertex)을 사이클(cycle) 없이 잇는 간선(edge) 묶음 가운데 값의 합이 가장 작은 것입니다. 간선은 늘 정점 수 − 1 개입니다. 크루스칼은 값이 작은 간선부터 보며 사이클이 생기는 간선만 버리고, 프림은 한 정점에서 시작해 지금까지 만든 트리 밖으로 나가는 가장 싼 간선을 하나씩 붙입니다. 두 방법은 같은 합에 닿습니다. 한 정점에서 가는 최단 경로(다익스트라)와는 다른 문제입니다.

위에서 방법을 고르고 「다음」을 누르세요. 초록 굵은 간선이 고른 간선, 흐린 점선과 값에 가로줄이 그어진 것이 버린 간선, 주황 띠와 주황 테두리가 이번 걸음에 본 간선입니다. 주황 화살표는 이번 걸음의 일입니다: 아래 간선 목록에서는 지금 보는 간선, 그래프에서는 고른 간선이 잇는 쪽(합쳐지는 연결 요소, 들어오는 정점)이고, 주황 점선은 사이클이 되는 길입니다. 크루스칼에서 정점 옆 작은 번호는 연결 요소(connected component) 번호로, 번호가 같으면 같은 연결 요소입니다. 프림에서는 연한 초록 영역이 트리, 그 테두리가 경계, 파란 점선이 경계를 건너는 간선(후보)입니다. 그래프와 값은 지어낸 것입니다.

1. 문제: 모든 정점을 가장 싸게 잇기

정점(점) 몇 개와, 두 정점을 잇는 간선이 있습니다. 간선마다 값, 곧 가중치(weight)가 붙어 있습니다. 마을과 마을 사이에 전선을 깔 수 있는 자리와 그 공사비를 떠올리면 됩니다. 할 일은 간선을 골라 모든 정점이 이어지게 하되, 고른 간선 가중치의 합이 가장 작게 하는 것입니다.

이렇게 고른 간선 묶음은 두 규칙을 지킵니다.

모든 정점을 사이클 없이 잇는 간선 묶음을 신장 트리라고 부르고, 그 가운데 합이 가장 작은 것을 최소 신장 트리라고 부릅니다. 재는 값은 이것 하나입니다.

W(T) = w(e₁) + w(e₂) + … + w(e_{V−1})

실험의 그래프는 정점 7개, 간선 12개이고, 최소 신장 트리의 합은 24 입니다.

2. 크루스칼: 싼 간선부터, 사이클은 버린다

  1. 간선을 값이 작은 순서로 늘어놓습니다.
  2. 하나씩 봅니다. 두 끝이 아직 다른 연결 요소면 고릅니다. 두 연결 요소가 하나가 됩니다.
  3. 두 끝이 이미 이어져 있으면 버립니다. 고르면 사이클이 생기기 때문입니다.
  4. 간선 V − 1 개를 고르면 멈춥니다.

처음에는 정점마다 따로인 연결 요소 7개가 있고, 간선을 하나 고를 때마다 연결 요소가 하나씩 줄어 마지막에 하나가 됩니다. 「두 끝이 이미 이어져 있나」를 빨리 묻는 방법은 5절에서 봅니다.

① B–F 3: 다른 연결 요소 6513 BCFE 2355 고름: 연결 요소 2 → 연결 요소 5 ② B–C 6: 같은 연결 요소 6513 BCFE 5555 사이클 B–F–C–B 가 생겨 버림
크루스칼이 간선 하나를 볼 때. 정점 옆 작은 번호는 연결 요소 번호입니다(실험과 같음). ① 두 끝의 번호가 다르면 고르고, 두 연결 요소가 하나가 됩니다. ② 번호가 같으면 두 끝을 잇는 길(주황 점선)이 이미 있어 고르면 사이클이 되니 버립니다. A, D, G 와 그쪽 간선은 뺐습니다.

해 볼 것. 크루스칼로 「다음」을 누르면 간선마다 두 걸음씩 갑니다. 먼저 두 끝의 연결 요소 번호를 비교하고, 다음 걸음에 고르거나 버립니다. 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. 프림: 트리를 한 정점씩 키운다

  1. 아무 정점 하나로 연결 요소를 시작합니다. 실험은 A 에서 시작합니다.
  2. 연결 요소 안의 정점과 밖의 정점을 잇는 간선 가운데 가장 싼 것을 고르고, 밖에 있던 정점을 연결 요소에 넣습니다.
  3. 두 끝이 모두 연결 요소 안이 된 간선은 다시 쓸 일이 없으니 버립니다.
  4. 모든 정점이 들어오면(간선 V − 1 개) 멈춥니다.
① 경계를 건너는 간선을 비교함 43678 가장 쌈 ABCFE 가장 싼 것은 B–F 3 ② B–F 3 을 고르고 F 를 넣음 4367815 ABCFE A–F 7 은 두 끝이 안이라 버림
프림의 한 걸음. 연한 초록 영역이 트리, 그 테두리가 경계입니다. ① 경계를 건너는 간선(파란 점선)의 값을 비교합니다. ② 가장 싼 간선을 고르면 F 가 안으로 들어오고 경계가 넓어집니다. 이제 E–F 1 과 C–F 5 도 경계를 건너는 간선이 됩니다. D, G 와 그쪽 간선은 뺐습니다.

해 볼 것. 프림으로 바꾸면 정점마다 두 걸음씩(경계를 건너는 간선을 비교하고, 가장 싼 것을 고름) 가며 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. 손으로 따라가기

실험과 같은 그래프입니다. 크루스칼은 값 순서로 간선을 봅니다.

차례간선값두 끝이 이미 이어져 있나한 일합
1E–F1아니오고름1
2D–G2아니오고름3
3B–F3아니오고름6
4A–B4아니오고름10
5C–F5아니오고름15
6B–C6예(B–F–C)버림15
7A–F7예(A–B–F)버림15
8A–E8예(A–B–F–E)버림15
9C–D9아니오고름. 간선 6개라 끝24

프림은 A 에서 시작해 트리 밖으로 나가는 간선만 봅니다.

차례연결 요소밖으로 나가는 간선(값)고른 간선(그 가운데 가장 싼 것)합
1AA–B 4, A–F 7, A–E 8A–B4
2A, BB–F 3, B–C 6, A–F 7, A–E 8B–F7
3A, B, FE–F 1, C–F 5, B–C 6, A–E 8, F–G 10E–F8
4A, B, F, EC–F 5, B–C 6, F–G 10, E–G 12C–F13
5A, B, F, E, CC–D 9, F–G 10, C–G 11, E–G 12C–D22
6A, B, F, E, C, DD–G 2, F–G 10, C–G 11, E–G 12D–G24

5. 「이미 이어져 있나」를 빨리 묻기: 유니온 파인드

크루스칼은 간선마다 「두 끝이 이미 이어져 있나」를 묻습니다. 물을 때마다 고른 간선을 따라 길을 찾으면 그래프를 다시 훑어야 합니다. 유니온 파인드는 이 물음에 빨리 답하는 작은 자료 구조입니다.

정점 둘을 고르고 「잇기」나 「같은 연결 요소인가」를 누르세요. 화살표는 그 정점의 칸이 가리키는 정점입니다. 방금 루트까지 따라 올라간 길과 그 칸이 주황으로 칠해집니다. 그림은 아래 표의 칸을 트리로 그린 것입니다.

해 볼 것. 크루스칼이 고른 차례대로 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)이라고 부릅니다. 출처의 성질은 이렇습니다: 교차 간선 가운데 가장 싼 것은 반드시 최소 신장 트리에 들어 있습니다(가중치가 모두 다를 때). 두 무리는 결국 어느 간선으로든 이어져야 하고, 그 간선은 가장 싼 교차 간선이라는 뜻입니다.

매 걸음 지금 가장 좋아 보이는 것을 고르고 되돌리지 않는 방식을 탐욕 알고리즘이라고 부릅니다. 출처는 두 방법을 모두 탐욕 알고리즘의 한 경우로 설명합니다. 탐욕이 늘 맞는 답을 내지는 않는데, 이 문제에서는 컷 성질이 맞는다는 것을 보장합니다.

7. 꼭 알아야 할 성질

성질쉬운 말실험에서
간선은 V − 1 개, 사이클 없음정점 V 개를 사이클 없이 모두 이으면 간선은 꼭 V − 1 개정점 7개, 고른 간선 6개
값이 모두 다르면 하나뿐최소 신장 트리가 하나라서 어느 방법으로 구해도 같은 간선이 나온다크루스칼과 프림이 같은 6개를 고른다
값이 0 이나 음수여도 된다값은 거리가 아니어도 된다. 크루스칼과 프림은 그대로 돈다자가 검사: 모든 값에서 5 를 빼도 같은 간선, 합 −6
최단 경로와 다르다트리 위의 두 정점 사이 길이 최단 경로는 아닐 수 있다D 에서 F: 트리 위 14, 최단 경로 12
그래프가 이어져 있어야 한다끊긴 그래프에는 신장 트리가 없다. 조각마다 따로 구한다자주 묻는 것 3

8. 언제 무엇을 쓰나

걸리는 시간은 출처의 「가장 나쁠 때」입니다. 출처는 가장 좋을 때와 보통은 따로 적지 않습니다.

방법걸리는 시간(가장 나쁠 때)더 드는 메모리좋은 점나쁜 점쓰는 경우
크루스칼E log E. 간선이 두 배면 두 배보다 조금 더간선 수 E 에 비례간선 목록만 있으면 된다. 정렬과 유니온 파인드로 짧게 짠다간선 전체를 값 순서로 다뤄야 한다간선이 적을 때, 자료가 간선 목록으로 올 때
프림(게으른 판)E log EE 에 비례우선순위 큐 하나로 트리를 키운다안쪽이 된 간선도 큐에 남겨 두었다가 꺼낼 때 버린다짜기 쉬운 프림이 필요할 때
프림(서두르는 판)E log V정점 수 V 에 비례밖의 정점마다 트리로 오는 가장 싼 간선 하나만 큐에 둔다값을 줄일 수 있는 우선순위 큐가 필요하다간선이 적거나 보통일 때
프림(배열 판)V². 정점이 두 배면 네 배V 에 비례큐 없이 배열을 훑어 가장 가까운 정점을 찾는다간선이 적어도 V² 이 든다간선이 아주 많을 때. 출처는 빽빽한 그래프에 가장 알맞다고 적는다

간선이 적을 때(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)

출처

← 다익스트라그리디 →