0x08. 최소 신장 트리

최소 신장 트리(MST)란?

신장 트리(Spanning Tree) 란 그래프의 모든 정점을 포함하면서 사이클이 없는 부분 그래프다. 즉, Spanning Graph이면서 동시에 Tree(acyclic)인 구조를 말한다.

여기서 한 걸음 더 나아간 것이 최소 신장 트리(Minimum Spanning Tree, MST) 문제다. (구현 문제 풀이는 MST 구현 참고) 연결된(connected), 무방향(undirected), 가중치(weighted) 그래프가 주어졌을 때, 모든 정점을 연결하면서 간선 가중치의 총합이 최소인 신장 트리를 찾는 것이 목표다.

좀 더 형식적으로 정리하면 다음과 같다.

• 무방향 그래프 G = (V, E)
• 각 간선 (u, v) $\in$ E에 가중치 w(u, v)가 존재
• G의 신장 트리 G'는 G의 최소 부분 그래프(Minimal Subgraph) 로서
  • V(G') = V(G) 이고 G'는 연결되어 있어야 한다
  • 정점이 n개인 연결 그래프는 최소 n-1개의 간선을 가져야 하며, 정확히 n-1개의 간선을 가진 연결 그래프는 반드시 트리다

핵심은 "연결 + n개 정점 + n-1개 간선 = 사이클 없음" 이라는 성질이다.

따라서 MST 문제는 간선 집합 T $\subseteq$ E를 찾는 것으로, T가 모든 정점을 연결(신장 트리)하면서 가중치 합 w(T) = $\sum_{(u,v) \in T}$ w(u, v)를 최소화하는 것이다. MST는 n-1개의 간선을 가지고, 사이클이 없으며, 유일하지 않을 수 있다.

실생활 비유를 들자면, n개의 핀을 n-1개의 전선으로 연결하되 각 전선이 두 핀을 잇고, 사용하는 전선의 총 길이를 최소화하는 문제와 같다.

이 문제를 해결하는 대표적인 그리디(Greedy) 알고리즘 두 가지가 있다.

• Kruskal 알고리즘
• Prim 알고리즘

MST를 구성하는 일반적 전략

MST를 어떻게 만들어 나갈까? 핵심 아이디어는 간선 집합 A를 점진적으로 확장하는 것이다.

1. 처음에 A는 빈 집합이다
2. 간선을 하나씩 A에 추가하면서, A의 간선 수가 n-1이 되면 종료한다
3. 매 단계마다 루프 불변성(Loop Invariant) 을 유지한다: A는 항상 어떤 MST의 부분집합이어야 한다

불변성을 유지하려면 A에 추가해도 괜찮은, 이른바 안전한 간선(Safe Edge) 만 추가해야 한다. 간선 (u, v)가 A에 대해 안전하다는 것은, A $\cup$ { (u, v) }도 여전히 어떤 MST의 부분집합이라는 뜻이다.

Generic MST 알고리즘

여기서 "safe"한 간선이란 그리디 관점에서 가장 좋아 보이는(smallest or largest) 간선을 의미한다.

안전한 간선을 찾는 방법: Cut과 Light Edge

안전한 간선을 찾기 위해 컷(Cut) 이라는 개념이 필요하다. S $\subset$ V이고 A $\subseteq$ E일 때 다음과 같이 정의한다.

컷(Cut)

(S, V - S)는 정점 집합 V를 두 개의 서로소(disjoint) 집합 S와 V - S로 나누는 분할(Partition) 이다.

간선이 컷을 교차(cross)한다

간선 (u, v) $\in$ E가 컷 (S, V - S)를 교차한다는 것은, 한 끝점이 S에 있고 다른 끝점이 V - S에 있다는 뜻이다.

컷이 A를 존중(respect)한다

컷 (S, V - S)가 A를 존중한다는 것은, A의 어떤 간선도 이 컷을 교차하지 않는다는 뜻이다. 다시 말해, A에 이미 포함된 간선들은 모두 컷의 한쪽에만 속한다.

경량 간선(Light Edge)

컷을 교차하는 간선 중 가중치가 최소인 간선을 경량 간선이라 한다. 동일한 가중치를 가진 간선이 여러 개 있다면 경량 간선도 여러 개일 수 있다.

정리(Theorem): 경량 간선은 안전하다

A가 어떤 MST에 포함된 E의 부분집합이고, (S, V - S)가 A를 존중하는 컷이며, (u, v)가 이 컷을 교차하는 경량 간선이라 하자. 그러면 (u, v)는 A에 대해 안전하다.

1. A를 포함하는 MST T가 존재한다고 하자. 그리고 T가 경량 간선 (u, v)를 포함하지 않는다고 가정한다.
2. A $\cup$ { (u, v) }를 포함하는 또 다른 MST T'를 구성할 것이다.
3. 간선 (u, v)를 T에 추가하면 u에서 v로 가는 경로 p와 함께 사이클이 형성된다. T에는 원래 n-1개의 간선이 있었는데 하나가 추가되어 n개가 되기 때문이다.
4. u와 v가 컷 (S, V - S)의 반대편에 있으므로, T에서 u에서 v로 가는 경로 p 위에 이 컷을 교차하는 간선이 최소 하나 존재한다. 이 간선을 (x, y)라 하자.
5. (x, y)를 제거하면 T가 두 개의 컴포넌트로 분리되고, (u, v)를 추가하면 다시 연결되어 새로운 신장 트리 T' 가 된다.

w(T') = w(T) - w(x, y) + w(u, v) ≤ w(T)

(u, v)는 경량 간선이므로 w(u, v) ≤ w(x, y)다. 따라서 T'도 MST다. 그리고 A $\cup$ { (u, v) } $\subseteq$ T'이므로, (u, v)는 A에 대해 안전하다.

따름정리(Corollary)

A가 그래프 G의 어떤 MST에 포함된 E의 부분집합이고, C = (V$_c$, E$_c$)가 포리스트 G$_A$ = (V, A)에서의 연결 컴포넌트(트리)라 하자. (u, v)가 C를 G$_A$의 다른 컴포넌트에 연결하는 경량 간선이면, (u, v)는 A에 대해 안전하다.

증명은 간단하다. 컷 (V$_c$, V - V$_c$)는 A를 존중하고, (u, v)는 이 컷에 대한 경량 간선이다. 따라서 위의 정리에 의해 (u, v)는 A에 대해 안전하다.

Kruskal 알고리즘

Kruskal 알고리즘의 동작 원리는 직관적이다.

1. 모든 간선을 가중치 기준으로 오름차순(nondecreasing order) 정렬한다
2. 정렬된 순서대로 간선을 하나씩 살펴보면서, 사이클을 형성하지 않는 간선만 추가한다
3. 사이클을 형성하는 간선은 버린다(discard)

이 알고리즘에서 A는 포리스트(Forest), 즉 여러 개의 트리 집합을 유지한다. 처음에는 각 정점이 하나의 트리이고, 간선을 추가할 때마다 두 컴포넌트가 하나로 합쳐진다. 최종적으로 하나의 큰 트리가 완성된다.

본질적으로, 매 단계에서 두 컴포넌트 사이의 컷을 교차하는 경량 간선을 선택하는 것이다. 이는 전형적인 그리디(Greedy) 전략이다.

의사 코드

실행 예시

Prim 알고리즘

Prim 알고리즘은 Kruskal과 다르게 처음부터 하나의 트리를 확장해 나가는 방식이다. Kruskal이 포리스트를 유지하는 반면, Prim에서는 A가 항상 하나의 트리다.

동작 과정은 다음과 같다.

1. 임의의 정점을 루트(root) r로 선택한다
2. 매 단계에서 현재 트리의 정점 집합 V$_A$와 나머지 정점 집합 V - V$_A$ 사이의 컷을 교차하는 경량 간선을 찾아 추가한다
3. $\pi$[v] 는 정점 v의 부모를 나타내며, 부모가 없거나 v가 루트이면 NIL이다

경량 간선을 빠르게 찾기 위해 우선순위 큐(Priority Queue) Q를 사용한다.

동작 개요

의사 코드

연습 문제

수업 중 연습 문제

Prim 알고리즘에 사용되는 자료 구조

Prim 알고리즘에서 핵심적으로 사용되는 자료 구조는 우선순위 큐(Priority Queue) 다. 우선순위 큐를 사용한다는 점에서 그리디 알고리즘임을 유추할 수 있다.

그렇다면 그리디 알고리즘은 반드시 우선순위 큐만 사용하는가? 그렇지 않다. 정렬된 배열(Sorted Array) 과 우선순위 큐 모두 사용할 수 있다. 하지만 둘 사이에는 중요한 차이가 있다. key 값이 변경되었을 때, 정렬된 배열은 다시 정렬해야 하므로 O(n log n)이 소요되지만, 우선순위 큐는 O(log n) 만에 처리할 수 있다. 이 차이가 Prim 알고리즘에서 우선순위 큐를 선택하는 이유다.

HGU 전산전자공학부 용환기 교수님의 23-1 알고리듬 분석 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.