우선 '최소 스패닝 트리'가 무엇을 뜻하는 단어인지 먼저 알아봅시다.
우선 '트리'란, 사이클을 갖지 않는 연결 그래프를 뜻합니다.
정점이 \(V\)개인 트리는 \(V-1\)개의 간선으로 모두 연결되어 있게 됩니다.
'그래프의 스패닝 트리'는, 그래프에서 일부의 간선을 선택해 만든 트리를 뜻합니다.
따라서 이 연결 그래프는
다음과 같은 스패닝 트리를 가질 수 있게 됩니다.
물론 위 2가지의 형태가 아닌 다른 형태의 스패닝 트리도 존재합니다.
'그래프의 최소 스패닝 트리'는, 가중치가 있는 연결 그래프에서 간선의 가중치의 합이 가장 작은 스패닝 트리를 말합니다.
따라서 이 연결 그래프의 최소 스패닝 트리는
이런 형태가 됩니다.
가중치의 합은 17로, 가중치의 합이 이보다 작은 스패닝 트리는 만들 수 없습니다.
그러면 그래프의 최소 스패닝 트리(Minimum Spanning Tree, MST)를 구하는 알고리즘에 대해 알아봅시다.
https://www.acmicpc.net/problem/1197
1. 크루스칼 알고리즘 (Kruskal's Algorithm)
그래프의 간선을 가중치가 작은 순으로 정렬합니다.
그 후 그리디하게 가장 작은 가중치를 가지는 간선 부터 MST에 추가합니다.
간선 \((u,v)\)를 추가할 때, 정점 \(u\)와 \(v\)가 이미 연결되어 있다면 무시합니다.
두 정점 \(u\)와 \(v\)가 연결 되어 있는지 여부는 어떻게 빠르게 알 수 있을까요?
유니온-파인드 자료구조를 이용합니다.
두 정점이 연결 되어있는지 여부는 두 정점이 같은 집합안에 포함되어 있는지 확인하는 연산으로,
\(u\)와 \(v\)를 간선으로 이을 때는 \(u\)가 포함된 집합과 \(v\)가 포함된 집합을 합치는 연산을 함으로써 구현할 수 있습니다.
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
const int N = 10001;
int v, e;
int par[N];
int height[N];
int getPar(int a)
{
if (par[a] == -1) return a;
else return par[a] = getPar(par[a]);
}
void merge(int a, int b)
{
a = getPar(a);
b = getPar(b);
if (a == b) return;
if (height[a] > height[b])
par[b] = a;
else
{
par[a] = b;
if (height[a] == height[b]) height[b]++;
}
}
// Union-Find 자료구조
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
memset(par, -1, sizeof par);
cin >> v >> e;
vector < pair<int, pii> > edge;
// {가중치, {u,v}} 를 저장하는 간선 리스트
for (int i = 0; i < e; i++)
{
int u, v, w;
cin >> u >> v >> w;
edge.push_back({ w,{u,v} });
}
sort(edge.begin(), edge.end()); // 가중치가 작은 순으로 정렬한다.
int cnt = 0;
int ans = 0;
for (auto it : edge)
{
if (cnt == v - 1) break;
// 이미 모든 정점이 연결되었다면 종료한다.
int u = it.second.first;
int v = it.second.second;
int w = it.first;
if (getPar(u) == getPar(v)) continue;
// u와 v가 이미 연결된 상태라면 무시한다.
merge(u, v);
// u와 v를 잇는 간선을 만든다.
cnt++;
ans += w;
}
cout << ans;
}
|
시간복잡도를 계산해봅시다.
우선 간선들을 정렬하는데 시간복잡도는 \(O(E\log E)\),
각 간선에 대해 유니온-파인드 자료구조의 연산을 하는데 시간복잡도는 \(O(E \times (\approx 1))\) 입니다.
따라서 가장 큰 시간복잡도를 가지는 부분은 간선을 정렬하는 부분이며,
총 시간복잡도는 \(O(E\log E) = O(E\log V)\) 입니다.
2. 프림 알고리즘 (Prim's Algorithm)
시작 정점을 하나 선택합니다.
이 정점에서 다른 정점과 연결된 간선 중에 가중치가 가장 작은 것을 선택해 MST에 추가합니다.
이런식으로 지금까지 선택된 모든 정점과 선택되지 않은 모든 정점 간 연결된 간선 중,
가장 작은 것을 선택해 MST에 추가하는 것을 반복합니다.
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
const int N = 10001;
int v, e;
vector <pii> graph[N];
// 인접 리스트
bool isSelected[N];
// 현재 이 정점을 선택했는지 여부
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> v >> e;
for (int i = 0; i < e; i++)
{
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({ v,w });
graph[v].push_back({ u,w });
}
isSelected[1] = 1; // 1번 정점을 시작으로 한다.
priority_queue <pii> pq;
// 지금까지 선택된 정점에 연결된 간선 중 가중치가 가장 작은 것을 선택하기 위해 힙을 이용한다.
// {가중치, 상대 정점}이 저장되어 있다.
for (auto it : graph[1])
{
// 1번 정점과 연결된 간선들을 힙에 넣어준다.
int nv = it.first;
int w = it.second;
pq.push({ -w, nv });
// pq는 기본적으로 가장 큰 수를 우선순위가 높다고 판단하기 때문에, 부호를 바꿔 넣어준다.
}
int cnt = 1;
int ans = 0;
while (cnt < v)
{
auto it = pq.top(); pq.pop();
int v = it.second;
int w = -it.first;
if (isSelected[v]) continue;
// 이미 선택된 정점이라면 무시한다.
isSelected[v] = 1;
for (auto it : graph[v])
{
// 지금 추가된 정점 v와 연결된 간선들을 힙에 넣어준다.
int nv = it.first;
int w = it.second;
if (isSelected[nv]) continue;
// 역시 이미 선택된 정점이라면 무시한다.
pq.push({ -w, nv });
}
cnt++;
ans += w;
}
cout << ans;
}
|
시간복잡도를 계산해봅시다.
각 간선들을 최대 1번씩 살펴보고, 힙에서의 삽입, 삭제 비용은 각각 \(O(\log E)\)입니다.
따라서 총 시간복잡도는 \(O(E\log E) = O(E\log V)\) 입니다.
제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.
https://www.acmicpc.net/group/7712
'알고리즘 > 그래프' 카테고리의 다른 글
Euler tour technique (0) | 2020.06.15 |
---|---|
최소 공통 조상 (0) | 2020.05.11 |
위상 정렬 (0) | 2020.05.10 |
최단 경로 (0) | 2020.04.29 |
그래프 탐색 (DFS, BFS) (0) | 2020.04.28 |