크루스칼 알고리즘
- MST(Minimum Spanning Tree, 최소 신장 트리)
- 모든 간선에 대해 가장 가중치가 작은 간선부터 연결해주면서 최소 스패닝 트리를 만들어 나가는 알고리즘을 의미한다.
- 가장 작은 간선부터 간선을 연결하되, 연결하는 도중 사이클이 생기게 된다면 가중치가 작은 간선이어도 무시하여야 한다.
- 유니온 파인드(Union-Find) 알고리즘을 통해 구할 수 있다.
-
두 개의 트리를 연결하는 모든 간선 중 가장 작은 간선( u , v )를 찾아 MST의 부분집합에 추가한다.
-
그래프의 초기모습
정점 안의 숫자는 정점의 인덱스이고, 색은 대표값(유니온 파인드에서 부모의 값->같은집합인지 알기위함)을 뜻한다.
즉, 초기값에서는 각 정점이 각각의 집합을 이루도록 한다.
- 가장 작은 가중치부터 검사한다.
가중치가 가장 작은 간선( 3, 6 )을 선택한다.
Step1에서 정점 3은 밝은 회색이고, 정점 6은 진한 파란색이므로 두 정점은 다른 집합임을 알 수 있다.
이처럼 Find 연산을 통해 대표 값을 확인하였고, 두 집합이 다른 것이 확인되었으므로 Union을 수행한다.
4.위와 같은 과정을 반복한다.
코드
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef struct kruskal {
int from;
int to;
int val;
}KS;
vector<KS> edge;
int parent[10002];
int res; //트리의 최소가중치
bool chk;
bool comp(KS d1, KS d2)
{
return d1.val < d2.val;
}
// 파인드
int find(int u)
{
if (u == parent[u])
return u;
return parent[u] = find(parent[u]);
}
// 유니온
void merge(int u, int v)
{
chk = false;
u = find(u);
v = find(v);
// 사이클 존재 여부 확인 코드
if (u == v)
return;
parent[u] = v;
chk = true;
}
int main()
{
int V, E;
scanf("%d %d", &V, &E);
// 부모를 자기 자신으로 초기화
for (int i = 1; i <= V; i++)
parent[i] = i;
// 그래프 형성
for (int i = 0; i < E; i++)
{
KS ks;
scanf("%d %d %d", &ks.from, &ks.to, &ks.val);
edge.push_back(ks);
}
// 크루스칼 알고리즘에 의해 간선을 오름차순 정렬
sort(edge.begin(), edge.end(), comp);
// 간선 union, 사이클이 존재하지 않도록
for (int i = 0; i < E; i++)
{
merge(edge[i].from, edge[i].to);
if(chk)
res += edge[i].val;
}
cout << res <<endl;
return 0;
}
시간복잡도
union-find 알고리즘을 이용하면 union-find 의 시간복잡도는 상수이므로 Kruskal 알고리즘의 시간 복잡도는 간선들을 정렬하는 시간에 좌우된다. 즉, 간선 E개를 퀵 정렬과 같은 효율적인 알고리즘으로 정렬한다면 Kruskal 알고리즘의 시간 복잡도는 O(Elog₂E) 이 된다.
크루스칼 알고리즘 vs 프림 알고리즘**
그렇다면 언제 크루스칼 알고리즘을 쓰고, 언제 프림 알고리즘을 쓰면 좋을까?
이에따른 정답은 시간 복잡도로 생각해 보면 좋을 것 같다.
크루스칼 알고리즘 시간 복잡도 :: O(ElogE)
프림 알고리즘 시간 복잡도 :: O(ElogV)
결국, 간선의 개수가 작은 경우에는 크루스칼 알고리즘을, 간선의 개수가 많은 경우에는 프림 알고리즘이 더 좋다는 것이 자명하다.
참고
https://victorydntmd.tistory.com/101?category=686701
https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html
https://www.crocus.co.kr/733