크루스칼 알고리즘이란?
- MST(최소 신장 트리)를 찾는 알고리즘.
- Greedy method(탐욕적 방법)을 이용한다.
- Union-Find를 이용하여 사이클 탐색한다.
유니온 파인드를 모른다면 유니온 파인드를 먼저 읽어야 한다.
크루스칼의 핵심 개념은 간선을 거리가 짧은 순서대로 그래프에 포함시키는 것이다.
모든 노드를 최소 비용으로 연결시키는 것이 목적이기 때문이다.
크루스칼 동작 원리
주어진 그래프는 다음과 같다.
모든 간선중에 가중치가 가장 작은 간선을 선택한 후
유니온 파인드를 이용하여 사이클이 형성되는지 판별한다.
사이클이 형성되지 않기 때문에 해당 간선을 그래프에 추가한다.
다음으로 가중치가 작은 간선을 선택하고 사이클이 형성되는지 판별한다.
사이클이 형성되지 않기 때문에 해당 간선을 그래프에 추가한다.
앞의 과정을 반복한다.
선택한 간선의 두 노드가 이미 연결되어 있기 때문에
연결하게 되면 사이클을 형성한다.
따라서 그래프에 추가하지 않고 넘어간다.
해당 간선까지 그래프에 추가하게 되면
총 노드의 개수 - 1 = 7개의 간선이 그래프에 추가되었고 MST그래프가 형성된다.
나머지 노드들을 다 봐줘도 되지만
노드개수 - 1개의 간선이 선택되면 끝내는게 시간복잡도에 조금 더 좋을 것이다.
크루스칼 구현 방법
이제 크루스칼의 원리를 알았기 때문에 구현하는 것은 어렵지 않다.
우선 모든 간선들을 가중치 기준으로 오름차순 정렬시키는 과정이 필요하다.
이것은 sort를 써도 되고 우선순위 큐를 사용해도 된다.
다만 sort는 퀵정렬로 nlogn의 시간복잡도를 가지지만
우선순위 큐는 logn의 시간복잡도를 가지므로 우선순위 큐를 추천한다.
간선이 정렬되고 나면 큐에서 하나씩 뽑으면서
해당 간선이 사이클을 형성하는지 유니온 파인드로 판별하고
사이클이 형성되지 않는다면 가중치를 추가하고
사이클이 형성된다면 그냥 버리면 된다.
그렇게 큐가 빌때까지 돌거나
n-1개의 간선이 연결되면 종료하면 된다.
크루스칼 코드 - 백준 1922번 네트워크 연결
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
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define MAX 100001
using namespace std;
int parent[MAX];
struct edge {
int st, end, distance;
};
struct cmp {
bool operator()(edge x, edge y) {
return x.distance > y.distance;
}
};
int find(int x) {
if (parent[x] == x)
return x;
return parent[x] = find(parent[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y)
return;
parent[y] = x;
}
bool isUnion(int x, int y) {
x = find(x);
y = find(y);
if (x == y)
return true;
return false;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
priority_queue<edge, vector<edge>, cmp>arr;
int n, m; cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c; cin >> a >> b >> c;
arr.push({ a,b,c });
}
for (int i = 0; i < MAX; i++)
parent[i] = i;
int sum = 0;
while (!arr.empty()) {
if (!isUnion(arr.top().st, arr.top().end)) {
sum += arr.top().distance;
merge(arr.top().st, arr.top().end);
}
arr.pop();
}
cout << sum;
return 0;
}