본문 바로가기

알고리즘/그래프

최소 스패닝 트리

우선 '최소 스패닝 트리'가 무엇을 뜻하는 단어인지 먼저 알아봅시다.

 

우선 '트리'란, 사이클을 갖지 않는 연결 그래프를 뜻합니다.

정점이 \(V\)개인 트리는 \(V-1\)개의 간선으로 모두 연결되어 있게 됩니다.

 

'그래프의 스패닝 트리'는, 그래프에서 일부의 간선을 선택해 만든 트리를 뜻합니다.

 

따라서 이 연결 그래프는

 

 

다음과 같은 스패닝 트리를 가질 수 있게 됩니다.

물론 위 2가지의 형태가 아닌 다른 형태의 스패닝 트리도 존재합니다.

 

'그래프의 최소 스패닝 트리'는, 가중치가 있는 연결 그래프에서 간선의 가중치의 합이 가장 작은 스패닝 트리를 말합니다.

 

따라서 이 연결 그래프의 최소 스패닝 트리는

 

 

이런 형태가 됩니다.

가중치의 합은 17로, 가중치의 합이 이보다 작은 스패닝 트리는 만들 수 없습니다.

 

 

그러면 그래프의 최소 스패닝 트리(Minimum Spanning Tree, MST)를 구하는 알고리즘에 대해 알아봅시다.

 

https://www.acmicpc.net/problem/1197

 

1197번: 최소 스패닝 트리

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝

www.acmicpc.net

 

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<intint> 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] == -1return 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, -1sizeof 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 - 1break;
        // 이미 모든 정점이 연결되었다면 종료한다.
 
        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<intint> 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

 

ANZ1217

무슨 내용을 넣어야 좋을까요?

www.acmicpc.net

 

'알고리즘 > 그래프' 카테고리의 다른 글

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