최소 신장 트리(MST: Minimum Spanning Tree)
최소 신장 트리
신장 트리란 그래프 $G$의 부분 그래프 중 트리의 조건을 만족하는 것이다. 다시 말해서, 그래프 $G$의 모든 정점을 하나 이상의 간선을 사용해 트리 형태로 연결한 것이다.
최소 신장 트리란 무방향 가중치 그래프의 신장 트리 중 간선의 가중치의 합이 최소인 신장 트리이다.
최소 신장 트리를 구현하는 알고리즘에는 크루스칼 알고리즘과 프림 알고리즘이 있다. 일반적으로 크루스칼 알고리즘을 사용하여 구현한다.
진행 방식(크루스칼 알고리즘)
- 선택한 적 없는 간선 중 가중치가 가장 작은 간선을 선택한다.
- 해당 간선을 트리에 추가했을 때 사이클이 생긴다면, 1번으로 돌아가서 다른 간선을 선택한다.
- 사이클이 생기지 않는다면 트리에 해당 간선을 추가하고 1번으로 돌아간다.
선택한 적 없는 간선 중 항상 가중치가 가장 작은 간선을 선택하므로 그리디 알고리즘의 일종이라고 볼 수 있다.
위의 그래프에 크루스칼 알고리즘을 사용해서 최소 신장 트리를 만들어 보자.
가중치가 가장 작은 간선 $E = (B, C)$이다. 연결해도 사이클이 생기지 않으므로 그대로 연결한다.
가중치가 가장 작은 간선 $E = (A, C)$이다. 연결해도 사이클이 생기지 않으므로 그대로 연결한다.
가중치가 가장 작은 간선 $E = (A, B)$이다. 하지만 $(A, B)$를 연결하면 $A-B-C$ 사이클이 생긴다. 따라서 해당 간선은 추가하지 않는다. 앞으로도 추가하지 않을 예정이므로 제외한다고 생각하면 된다.
가중치가 가장 작은 간선 $E = (B, D)$이다. 연결해도 사이클이 생기지 않으므로 그대로 연결한다. 이 때, 모든 정점이 트리 형태로 연결되었으므로, 위의 부분 그래프는 신장 트리이다. 또한 이 신장 트리의 간선의 가중치의 합이 최소이므로 최소 신장 트리이다.
완성된 최소 신장 트리이다.
구현
크루스칼 알고리즘은 유니온 파인드와 우선순위 큐를 사용하여 구현할 수 있다.
선택하지 않은 간선 중 가중치가 최소인 간선을 선택하는 것은 우선순위 큐로, 두 정점을 연결하는(간선을 선택하는)것은 유니온 파인드의 Find연산으로 구현하면 된다.
Find 연산을 진행할 때, 이미 두 정점의 parent가 같다면 두 정점 사이에 parent를 경유하는 경로가 있다는 뜻이므로 해당 간선을 연결하면 사이클이 생기게 된다.
6407번: 전력난의 코드이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long
using namespace std;
int n, m, total, spanningSum;
vector<tuple<int, int, int>> edge;
int parent[200000];
int treeSize[200000];
void Output() {
cout << total - spanningSum << '\n';
}
int Find(int cur) {
if(parent[cur] == cur) {
return cur;
}
return parent[cur] = Find(parent[cur]);
}
bool Union(int u, int v) {
u = Find(u);
v = Find(v);
if(u == v) {
return false;
}
if(treeSize[u] <= treeSize[v]) {
parent[u] = v;
treeSize[v] += treeSize[u];
}
else {
parent[v] = u;
treeSize[u] += treeSize[v];
}
return true;
}
void Solve() {
int cnt = 0;
sort(edge.begin(), edge.end());
for(int i = 0; i < edge.size(); i++) {
if(cnt == m - 1) {
return;
}
int w = get<0>(edge[i]);
int u = get<1>(edge[i]);
int v = get<2>(edge[i]);
if(Union(u, v)) {
spanningSum += w;
cnt++;
}
}
}
void Init() {
total = spanningSum = 0;
edge.clear();
for(int i = 0; i < m; i++) {
parent[i] = i;
treeSize[i] = 1;
}
for(int i = 0; i < n; i++) {
int x, y, z;
cin >> x >> y >> z;
edge.push_back({z, x, y});
total += z;
}
}
void Input() {
cin >> m >> n;
if(n == 0 && m == 0) {
exit(0);
}
Init();
}
int main() {
FastIO;
while(true) {
Input();
Solve();
Output();
}
}
시간 복잡도
크루스칼 알고리즘은 간선의 정렬 + 정점의 연결로 이루어져 있다. 간선의 정렬은 우선순위 큐를 이용하므로 $O(ElogE)$이고, 정점의 연결은 유니온 파인드를 이용하므로 (사실상)상수 시간복잡도를 가진다.
따라서, 크루스칼 알고리즘의 시간 복잡도는 $O(ElogE)$이다.