[MST] 최소 스패닝 트리

최소 스패닝 트리는 가중치가 있는 양방향 그래프에서 등장한다.
만약 가중치가 없다면(가중치가 모두 1이라면)
최적해가 무엇이냐가 아니라, 답이 존재하는가 부터 문제가 된다(SCC)
그렇기에 MST는 가중치가 존재하는 그래프에서 논하게 된다.
BOJ에서 기본문제를 찾을 수 있다. https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

대략 다음의 문제를 해결해야한다.
- 입력으로는 양방향 그래프가 주어진다.
- 가중치가 있는 양방향 그래프에서, 모든 정점을 최소의 비용을 들여서 '연결'하고 싶다.
(비용이란 간선들의 가중치의 합이다.)
-> MST를 이루는 그래프를 구하여라

최적해의 간선의 개수는 정점의 개수보다 하나 적다고 직관적으로 파악할 수 있다.
일반적으로 이를 해결하는 알고리즘은 두 종류가 있다.
첫번째는 프림(Prim) 알고리즘이고, 두번째는 크루스칼(Kruskal) 알고리즘이다.
프림 알고리즘은 '정점'을 기준으로 하며, 크루스칼은 '간선'을 기준으로 한다.
성능은 O(ElogV)정도로 비슷하며,
세세히 들어가면 희소그래프일수록 크루스칼이 유리하고, 밀집그래프일수록 프림이 유리하다.
※ 기본적으로 두 알고리즘 모두 O(ElogV)의 시간복잡도를 갖는다.

---

구현 방법과 시간복잡도

프림과 크루스칼의 시간복잡도 모두 O(ElogV)정도로 기억해도 사실 큰 상관은 없지만, 조금 더 자세히 들여다보겠다.
우선, O(logE) = O(logV) 이다. 그 이유는 아래와 같다.
정점이 1부터 V까지 존재하며 간선이 최다로 존재할때, 간선은 1부터 V중 두개를 중복없이 조합하는것과 같다.
즉, E의 최대개수는 (V * V - 1) / 2 이다. E = V^2인 셈이고, logV^2 = 2logV이므로,
빅오표기법에 따라 상수를 제거하면 logE=2logV -> O(logE)=O(logV)인 셈이다.

프림

1. 인접행렬과 선형탐색

BOJ [1197] : 최소 스패닝 트리 문제는 O(V^2)에도 해결할 수 있다.
아래는 dist배열을 사용해 구현한 프림알고리즘이 되겠다.

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
#include<limits.h>
using namespace std;
int v, e;
const int INF = INT_MAX;
vector <pair<int, int> >adj[10003];
bool visit[10003];
int dist[10003];
long long prim(void) {
    int i, j, cur = 0, min_dist = INF;
    long long sum = 0;
    for (int i = 1; i <= v; i++) {
        dist[i] = INF;
        visit[v] = false;
    }
    dist[1] = 0;
    for (i = 1; i <= v; i++) {
        cur = -1;
        min_dist = INF;
        for (j = 1; j <= v; j++) {
            if (visit[j] == false && dist[j] < min_dist) {
                min_dist = dist[j];
                cur = j;
            }
        }
        if (cur == -1)return (long long)INF;
        sum += min_dist;
        visit[cur] = true;
        for (auto edge : adj[cur])
            dist[edge.first] = min(dist[edge.first], edge.second);
    }
    return sum;
}
int main(void) {
    int i;
    scanf("%d %d", &v, &e);
    for (i = 0; i < e; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back(make_pair(b, c));
        adj[b].push_back(make_pair(a, c));
    }
    printf("%lld", prim());
    return 0;
}

 

프림알고리즘을 '인접행렬'로 구현할경우, 간선중 최소 가중치의 간선을 탐색하는데에 O(V)의 시간이 걸린다.
인접행렬 + 선형탐색으로 이루어진 프림은 O(V^2)의 시간복잡도를 갖는다.
이를 다익스트라 알고리즘의 개선과 같은 방식으로 개선할 수 있다.

2. 인접리스트와 이진힙

다익스트라의 O((E+V)logV)의 방법과 매우 유사하다.
다익스트라를 O(V^2)에만 구현해봤다면 다익스트라도 같이 보면 좋다.
다익스트라와 마찬가지로 '거리'내지 '비용'을 이진 힙에 넣어서 '선형탐색'대신 'pq.top()'으로 대체한다.
인접리스트와 우선순위큐로 구현한 프림의 시간복잡도는 O((E+V)logV) = O(ElogV)가 된다.

+) 이를 더욱 개선한 방법으로, '피보나치 힙'을 사용하면 O(E+VlogV)의 시간복잡도로 최적화도 가능하다.

크루스칼

우선, 크루스칼은 유니온-파인드 알고리즘을 사용한다.
그렇기에 유니온파인드 알고리즘의 시간복잡도에 직접적 영향을 받는다.
프림의 경우 탐색을 어떻게 구현하느냐가 성능에 정향을 주었다면,
크루스칼의 경우 유니온파인드를 어떻게 구현하느냐가 성능에 영향을 준다.
유니온파인드 알고리즘의 연산속도에 영향을 주는 요인중 하나는 트리의 높이(재귀의 깊이)이다.
크루스칼의 작동방식상 연산 도중에 여러개의 트리가 존재하며
이들의 트리의 높이를 '최대한 비슷하게' 유지시켜 주는등의 최적화가 가능하다.
다만, 이것이 빅오상에서 드러날정도의 최적화가 아니므로, O(ElogV)의 하나의 시간복잡도만 존재한다.