[알고리즘] 최소신장트리(MST)와 프림, 크루스칼 알고리즘 + 백준1197번

📂 최소신장트리 (Minimum Spanning Tree)

• 신장트리 : 그래프 G의 노드 V를 모두 포함하는 E에 속하는 에지를 사용해 만든 트리
• 최소신장트리 : 가중그래프 G의 신장트리 중에서 트리에 속한 가중치의 합을 최소로 하는 신장 트리
• 최소신장트리를 만드는 2가지 방법 : Prim's Algorithm, Kruskal's Algorithm

최소신장트리의 간선 개수는 (정점의 수 - 1) 이다. (N-1개의 간선으로 연결되어 있으면 필연적으로 모든 노드가 연결된다)

간선들의 가중치 합이 최소인 경우 서로 다른 최소신장트리가 하나 이상 있을 수 있다.

📂 크루스칼 알고리즘 (Kruskal's Algorithm)

가중치가 가장 작은 간선부터 차례대로 간선을 선택해 나가는 방법으로, 탐욕적(greedy) 방법을 사용한다.

매 단계 가중치가 가장 작은 간선을 연결하며, 이전 단계에서 만들어진 신장트리와는 상관없이 최소 간선을 선택한다.

크루스칼 알고리즘의 핵심은 에지를 정렬하는 것에 있다. 에지를 오름차순으로 정렬해서 가중치가 가장 작은 에지 순서대로 노드를 이어나간다. 에지 정렬은 O(ElogE)의 시간복잡도를 가진다. 

이때 사이클을 형성하지 않는 에지를 선택해야 한다. 사이클을 형성하게 되면 N-1개의 간선으로 N개의 정점을 이을 수 없기 때문이다. 사이클의 형성 여부는 Union-Find 알고리즘으로 확인한다.

Union-Find 알고리즘은 두 정점의 부모가 같다면 사이클이 형성되는 것이고, 두 정점의 부모가 다르다면 사이클이 형성되지 않는 것을 이용한다. 크게 Union(x, y)와 Find(x), Find(y)로 나눠볼 수 있다. Find(x)를 통해 x의 부모노드(root노드)를 확인하고, x와 y의 부모노드를 비교해 Union하는 방식이다. Union(x, y) 에서는 두 노드의 root노드가 같다면 이미 같은 트리이므로 다른 걸 해줄 필요가 없고, root노드가 다르다면 x의 root노드가 y가 되도록 설정해준다.

+ union-find는 구글링해서 찾아본거라 완벽하게 이해하진 않은 거 같다. 나중에 다시 봐야지

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 10000;

int v, e;
int parent[MAX + 1];

pair<int, pair<int, int>> edge[100000];

// n개의 원소가 각각의 집합에 포함되어 있도록 초기화
void Set() {
    for(int i = 1; i <= MAX; i++) {
        parent[i] = i;
    }
}

int Find(int x) {
    // root인 경우 x를 반환
    if(parent[x] == x) return x;
    // 아니면 root를 찾아감
    return parent[x] = Find(parent[x]);
}

// 두 원소 x, y가 주어질 때 이들이 속한 두 집합을 하나로 합침
// x와 y의 원소가 들어오면 각각의 root 노드를 찾아주고
// 두 root 노드가 같지 않다면 x의 root 노드를 y로 설정해준다
void Union(int x, int y) {
    int xParent = Find(x);
    int yParent = Find(y);
   
    if(xParent == yParent) return;  // root가 같다면 이미 같은 트리
    parent[xParent] = yParent; // u의 root가 v가 되도록
}

int main()
{
    cin >> v >> e;
    Set();
    for(int i = 0; i < e; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edge[i].first = c;
        edge[i].second.first = a;
        edge[i].second.second = b;
    }
    
    sort(edge, edge + e);
    int weight = 0;
    int count = 0;
    for(int i = 0; i < e; i++) {
        if(Find(edge[i].second.first) != Find(edge[i].second.second)) {
            weight += edge[i].first;
            Union(edge[i].second.first, edge[i].second.second);
            count++;
        }
        if(count == v - 1) break;
    }
    
    cout << weight;

    return 0;
}

📂 프림 알고리즘 (Prim's Algorithm)

프림 알고리즘은 정점 하나를 시작점으로 두고, 이전 단계에서 완성된 신장트리에 연결된 간선 중 가중치가 최소인 간선을 선택하는 방법이다. 해당 간선으로 연결된 정점이 현재의 신장트리에 속해있지 않다면 선택한다. 이때 지금까지의 신장트리와 연결된 간선 중에 최소인 것을 찾으려면 최소 우선순위 큐를 사용하면 빠르게 처리할 수 있다. 

또한 에지 = 노드의 수 - 1 이 될 때까지 반복해 에지를 탐색해 나간다. 최솟값을 찾을 때 최소 우선순위 큐를 사용한다면 O(nlogn)의 시간복잡도가 발생한다. 이전 단계에서 만든 신장트리와 연결된 간선을 모두 최소우선순위 큐에 삽입해 그 중 최소값을 찾아야 하므로 재귀적으로 구현해볼 수 있다. 찾은 최소값으로 노드와 신장트리를 연결하고, 그 노드를 기준으로 Prim() 함수를 재귀적으로 호출한다. 

개인적으로 크루스칼보다 프림알고리즘이 좀 더 이해하기는 쉬운 듯하다. 최소 우선순위 큐는 트리구조를 가지는 최소힙이라고 봐도 되는데, 시간복잡도 O(nlogn)을 가지는 최소값찾는 방법이라고 생각하고 넘기면 될 거 같다. "최소" 우선순위 큐를 구현하려면 비교함수로 greater<type>을 추가해주기!

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int v, e, sum;
vector<vector<pair<int, int>>> edge(10001);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pqueue;
bool visited[10001];

void Prim(int v) {
    visited[v] = true;
    
    // 정점 v와 연결된 간선을 큐에 담는다
    for(auto a: edge[v]) {
        if(!visited[a.second]) {
            pqueue.push({a.first, a.second});
        }
    }
    while(!pqueue.empty()) {
        pair<int, int> w = pqueue.top();
        pqueue.pop();
        if(!visited[w.second]) {
            sum += w.first;
            Prim(w.second);
            return;
        }
    }
}

int main()
{
    cin >> v >> e;
    int x, y, w;
    for(int i = 0; i < e; i++) {
        cin >> x >> y >> w;
        edge[x].push_back(make_pair(w, y));
        edge[y].push_back(make_pair(w, x));
    }
    Prim(1);
    
    cout << sum;
    
    return 0;
}