최소 신장 트리

요약

섬들을 다리로 모두 잇되, 다리 값의 합을 가장 적게 하고 싶다. 가장 싼 다리부터 보며, 이미 이어진 두 섬 사이의 다리면 건너뛰고 아니면 놓는다(크루스칼). 결과는 고리 없이 모든 섬을 잇는 나무가 되고, 섬이 n개면 다리는 n − 1개다. 단, 모든 섬이 이어질 수 있는 그래프여야 하고, 이렇게 만든 나무 위의 길이 두 섬 사이의 가장 짧은 길은 아니다.

예시로 보기

점 1 ~ 5와 간선 1–2(4), 1–3(1), 2–3(2), 2–4(5), 3–4(8), 3–5(10), 4–5(2)가 있다. 크루스칼은 간선을 비용 순으로 보며, 두 끝이 이미 같은 무리인지 유니온 파인드로 묻는다.

간선 (비용)	두 끝이 이미 이어졌나	한 일	무리
1–3 (1)	아니다	고름	{1, 3}
2–3 (2)	아니다	고름	{1, 2, 3}
4–5 (2)	아니다	고름	{1, 2, 3} {4, 5}
1–2 (4)	이어졌다	건너뜀(고리가 생긴다)
2–4 (5)	아니다	고름	{1, 2, 3, 4, 5}
3–4 (8), 3–5 (10)	이어졌다	건너뜀

고른 간선 4개의 합은 1 + 2 + 2 + 5 = 10이다.

flowchart LR
    n1(("1")) ===|"1"| n3(("3"))
    n2(("2")) ===|"2"| n3
    n4(("4")) ===|"2"| n5(("5"))
    n2 ===|"5"| n4
    n1 ---|"4"| n2
    n3 ---|"8"| n4
    n3 ---|"10"| n5

굵은 선이 고른 간선 4개이고, 가는 선이 건너뛴 간선 3개다. 가는 선을 하나라도 더하면 굵은 선과 함께 고리가 생긴다¹.

def kruskal(n, edges):                  # edges: (a, b, w), 점은 1 ~ n
    parent = list(range(n + 1))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # 가는 길에 한 칸씩 건너뛰게 줄인다
            x = parent[x]
        return x
    total = 0
    for a, b, w in sorted(edges, key=lambda e: e[2]):
        ra, rb = find(a), find(b)
        if ra != rb:                    # 다른 무리면 잇는다
            parent[rb] = ra
            total += w
    return total

맞는 이유

자르기 성질(cut property): 점들을 두 편으로 나눴을 때, 두 편을 잇는 간선 중 가장 싼 간선은 어떤 최소 신장 트리에 들어 있다².

증명 펼치기

두 편을 잇는 가장 싼 간선을 e라 하자. 최소 신장 트리 T가 e를 쓰지 않는다고 하자.
T에 e를 더하면 고리가 하나 생긴다. 그 고리는 두 편을 오가므로, e 말고도 두 편을 잇는 간선 f를 하나 지난다.
f를 빼면 다시 모든 점을 잇는 나무가 된다. e는 가장 싼 간선이라 비용 합은 늘지 않는다.
그래서 e를 쓰는 최소 신장 트리가 있다. ∎

크루스칼이 간선 a–b를 고르는 순간, “a의 무리”와 “나머지”로 나눈 두 편을 잇는 간선 중 a–b가 가장 싸다(더 싼 간선은 이미 다 봤고, 그중 두 편을 잇는 것은 없었다). 그래서 자르기 성질에 따라 고른 간선이 늘 안전하다. 이것은 그리디의 바꿔치기 논증이다.

프림: 한 점에서 시작해, “지금까지 이은 점들”과 “아직인 점들”을 잇는 가장 싼 간선을 힙으로 골라 하나씩 붙인다. 자르기 성질을 그대로 쓴 방법이다.

검증: 예시 표의 고름·건너뜀 순서와 합 10, 확인 문제 C1·C3의 답을 코드로 확인했다. 무작위 연결 그래프 1,500개(점 6개 이하)에서 크루스칼과 프림의 합이 “간선 n − 1개를 모두 골라 나무가 되는 것 중 가장 싼 것”과 같았다 — 28_mst_verify.py

활용

비용: 크루스칼은 간선 정렬 \(O(m \log m)\) + 유니온 파인드, 프림은 힙으로 \(O(m \log m)\)이다. 간선이 적으면 크루스칼이 짧고, 격자처럼 간선을 그때그때 만들 때는 프림이 편하다.
쓰는 곳: 전선·수도관·통신망을 가장 싸게 까는 설계, 비슷한 것끼리 묶기(비용이 큰 간선 몇 개를 빼면 무리가 나뉜다).
흔한 실수: 무리를 확인하지 않아 고리를 만든다. 그래프가 연결되지 않았는데 결과를 그대로 쓴다(고른 간선이 n − 1개인지 확인한다). 다익스트라의 최단 경로 트리와 헷갈린다(확인 문제 C3).

연결

선수: 유니온 파인드, 정렬과 정렬 기준, 그래프 표현, 트리
가장 싼 것부터 고르고 되돌리지 않는 그리디가 맞는 대표적인 예다.
자르기 성질 증명의 2단계는 트리의 동치 조건 4(트리에 없던 간선을 더하면 고리가 생긴다)다. 3단계는 동치 조건 5다. 고리 위의 f를 빼도 모두 이어져 있고 간선이 n − 1개라서 다시 트리다.
간선 a–b를 ‘a 칸 1, b 칸 −1, 나머지 0’인 벡터로 적으면, 고리가 없는 간선 모음은 선형독립이고 고리가 있는 모음은 선형종속이다. 그래서 연결 그래프의 신장 트리는 모든 간선 벡터가 만드는 공간의 기저다. 어느 신장 트리를 골라도 간선이 n − 1개인 것은 부분공간, 기저와 차원의 ‘기저의 개수는 늘 같다’와 같은 이야기다. 크루스칼의 if ra != rb:는 새 간선이 이미 고른 간선들과 독립인지 묻는 셈이다.
예시 표의 ‘무리’는 고른 간선으로 이어진 점끼리의 묶음이다. 아직 혼자인 점도 한 무리로 치면, 무리들은 동치관계와 분할의 분할이다. 간선을 하나 고를 때마다 두 무리가 하나로 합쳐진다.
연습: 지형 이동

과목별 관점

자료구조 (1-2학기). 자료구조에서는 신장 트리를 통신망 문제로 들여온다. 깔 수 있는 선 가운데 가장 적은 수만 골라 모든 도시를 이으려면, 사이클 위의 간선은 빼도 연결이 그대로라는 점을 써서 사이클을 모두 없앤다. 그렇게 남는 것이 간선 \(n - 1\)개짜리 나무다. 점 11개 예제에서 눈에 띄는 대로 고른 신장 트리는 비용이 51이고 최소 비용 신장 트리는 41이다. 자료구조 쪽이 이 문서에 더하는 것은 다음이다.

고르기 전략 셋, 버리기 전략 둘. 고르기는 크루스칼, 프림, 그리고 덩어리마다 가장 싼 간선을 한꺼번에 고르는 솔린의 방법이다. 버리기는 (1) 사이클을 찾아 그 위에서 가장 비싼 간선을 빼기를 사이클이 없을 때까지 하는 것, (2) 비싼 간선부터 보며 빼도 연결이 남으면 빼는 것이다. 간선 10개, 점 8개인 예제라면 7개를 고르든 3개를 버리든 같다. 다섯 방법 모두 최소 비용 신장 트리를 준다.
크루스칼의 자료구조와 시간. 간선 모음에서 할 일은 “가장 싼 간선을 꺼내 지우기”라서 간선을 최소 힙에 넣는다. 힙을 한꺼번에 만드는 데 \(O(m)\), 하나 꺼내는 데 \(O(\log m)\)이다(간선 수를 \(e\)로 적기도 한다). 고른 간선 모음에서 할 일은 “이 간선을 넣으면 사이클이 생기나”이고, 두 끝이 같은 덩어리인지로 판정한다. 덩어리를 점의 집합으로 두고 find와 union으로 다룬다. find는 많아야 \(2m\)번, union은 \(n - 1\)번이라 거의 \(O(n + m)\)이고, 힙에서 꺼내는 데 드는 \(O(m \log m)\)을 더해 전체가 \(O(n + m \log m)\)이다. 힙을 쓰는 크루스칼은 간선이 \(n - 1\)개 모이면 멈춘다. 위 코드처럼 먼저 다 정렬하는 것과 달리, 힙을 쓰면 남은 비싼 간선은 꺼내지도 않는다³.
프림의 시간. 자료구조에서는 프림을 가장 빠른 방법으로 꼽는다. 다익스트라의 배열 판과 같은 꼴로 짜면 \(O(n^2)\)이고, 피보나치 힙을 쓰면 \(O(m + n \log n)\)이다.
하나뿐인 답. 간선 비용이 모두 다르면 최소 비용 신장 트리는 하나뿐이다. 예제(비용 46)에서 크루스칼, 5에서 시작한 프림, 솔린이 같은 간선 일곱 개를 고르는 것이 그래서다(확인 문제 C4).
다른 비용 계산. 비용을 다르게 세는 문제도 있다. 한 도시가 전파를 쏘면 닿는 거리 안의 이웃이 모두 받는다고 보고, 나무에서 자식이 있는 점마다 “가장 먼 자식에게 닿는 힘” 한 번만 더한다. 비용 51짜리 신장 트리를 1번 도시에서 퍼지는 방송 트리로 세면 \(4 + 8 + 5 + 6 + 7 + 8 + 3 = 41\)이다. 간선 비용의 합을 줄이는 이 문서의 문제와는 다른 문제다³.

손으로 따라가는 문제는 그래프 탐색과 신장 트리 연습에 있다.

확인 문제

C1 간선 1–2(3), 1–3(1), 1–4(4), 2–3(2), 3–4(5)에 크루스칼을 돌린다. 고르는 간선과 비용 합은?

답: 1–3(1), 2–3(2)을 고르고, 1–2(3)는 1과 2가 이미 이어져 건너뛴다. 1–4(4)를 고르면 네 점이 모두 이어진다. 합은 7이다. 3–4(5)는 볼 필요도 없이 건너뛴다.

C2 크루스칼 코드에서 if ra != rb: 한 줄이 하는 일을 한 문장으로 말하라.

답: 간선의 두 끝이 이미 같은 무리(이미 이어진 상태)면 그 간선을 넣지 않아 고리가 생기지 않게 한다. 다른 무리일 때만 간선을 넣고 두 무리를 합친다.

C3 간선 A–B(2), B–C(2), A–C(3)에서 최소 신장 트리를 구하고, 그 나무 위의 A에서 C로 가는 길과 A에서 C로 가는 최단 경로를 비교하라.

답: 최소 신장 트리는 A–B, B–C(합 4)다. 나무 위의 A → C는 A–B–C로 4다. 최단 경로는 A–C 바로 3이다. 최소 신장 트리는 “모두 잇는 비용의 합”을, 최단 경로는 “두 점 사이 길의 비용”을 줄인다. 목적이 다르니 같은 나무가 나오지 않는다.

C4 간선 비용이 모두 다르면 최소 신장 트리가 하나뿐인 까닭은? 비용이 같은 간선이 있으면 여럿일 수 있음을 보이는 예도 하나 들어라.

답: 서로 다른 최소 신장 트리 \(T_1\), \(T_2\)가 있다고 하자. 둘 가운데 한쪽에만 있는 간선들 중 가장 싼 것을 \(e\)라 하고, \(e\)가 \(T_1\)에 있다고 하자. \(T_2\)에 \(e\)를 더하면 고리가 하나 생긴다. \(T_1\)에는 고리가 없으니, 그 고리에는 \(T_1\)에 없는 간선 \(f\)가 있다. \(f\)는 \(T_2\)에만 있는 간선이라 \(e\)보다 비싸다. \(T_2\)에서 \(f\)를 빼고 \(e\)를 넣으면 더 싼 신장 트리가 되어 \(T_2\)가 최소라는 것과 어긋난다. 예: 삼각형의 세 간선이 모두 1이면 어느 둘을 골라도 비용이 2라서 최소 신장 트리가 셋이다.
이유: “\(f\)가 \(e\)보다 비싸다”에서 비용이 모두 다르다는 조건을 쓴다. 같아도 되면 \(f\)와 \(e\)의 비용이 같을 수 있어 어긋남이 생기지 않는다³.

예시로 보기의 간선 일곱 개와 크루스칼 표의 고름·건너뜀 결과를 그대로 그렸다. ↩
자르기 성질과 그 증명은 Cormen 외, Introduction to Algorithms 3판, 23.1절 “Growing a minimum spanning tree”(정리 23.1)을 풀어 쓴 것이다. 크루스칼과 프림의 구현은 Laaksonen, Competitive Programmer’s Handbook (2018년 7월판), 15.1·15.3절. ↩
비용이 모두 다른 무작위 그래프 300개에서 신장 트리를 모두 만들어 최소인 것이 하나뿐임과 삼각형에서는 셋임을 37_sollin-algorithm_verify.py로, 방송 트리의 41을 37_graph-spanning-practice_p5.py로 확인했다. ↩ ↩² ↩³