최소 신장 트리(MST) 구하는 알고리즘 - 크루스칼 알고리즘, 프림 알고리즘

---

앞선 요약

 - 크루스칼 알고리즘은 Union Find 자료구조(=알고리즘)을 알고 있어야 합니다.

합집합 찾기 - Union Find, 유니온 파인드 알고리즘

 - 간선이 많은 경우 프림 알고리즘, 간선이 적은 경우 크루스칼 알고리즘을 사용하면 효율적입니다.

 - 본 포스팅은 백준의 1197번 MST 문제를 바탕으로 설명하고 있습니다.

 

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int v, e, res = 0, edgenum = 0;
pair<int, pair<int , int>> edge[100001];
int parents[10001];

int FindRoot(int x){
    if(x == parents[x])
        return x;
    return parents[x] = FindRoot(parents[x]);
}

void Merge(int x, int y){
    x = FindRoot(x);
    y = FindRoot(y);

    if(x == y)
        return;
    parents[x] = y;
}

int main(){
    scanf("%d %d", &v, &e);
    
    for(int i = 0; i <= v; i++)
        parents[i] = i;

    for(int i = 0; i < e; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        edge[i].first = c;
        edge[i].second.first = a;
        edge[i].second.second = b;
    }

    sort(edge, edge + e);
    
    // 간선 갯수만큼 크루스칼 알고리즘
    for(int i = 0; i < e; i++){
        if(FindRoot(edge[i].second.first) == FindRoot(edge[i].second.second))
            continue;
        
        Merge(edge[i].second.first, edge[i].second.second);
        res += edge[i].first;
        edgenum++;
        if(edgenum == v - 1)
            break;
    }
    printf("%d\n", res);
}

 크루스칼 알고리즘은 간선 위주의 연산을 진행하게 되며 사이클의 여부는 부모-자손 관계를 통해서 알아내게 됩니다. 알고리즘의 순서는 아래와 같습니다.

 

1. 입력값을 전부 받은 뒤 각 노드의 부모를 나타낼 배열 parent를 자기 자신으로 초기화해 줍니다.

2. 입력받아 저장해둔 간선들을 정렬해 길이가 가장 짧은 간선부터 연결을 해 줍니다.

3. 가장 짧은 간선으로 연결된 두 노드의 부모가 다르다면 이 둘을 연결해주고 부모-자식 관계를 업데이트해줍니다.

4. 만일 부모가 같다고 하면 해당 간선을 넘기고 다음 노트를 살펴봅니다.

5. 위 과정들을 반복하면서 연결된 횟수가 N-1 (노드 수 - 1)이라면 알고리즘을 종료합니다.

 

 위 과정을 그림으로 살펴보면 확실히 거리가 짧은 점들부터 탐색을 하며 중간중간 사이클을 이루게 될 시 간선 선택이 취소되는 모습을 볼 수 있습니다.

 

 뒤에 설명드릴 프림 알고리즘과 다르게 간선을 위주로 하나하나 찾아보게 되므로 간선을 정렬하는 시간으로 시간 복잡도는 O(ElogE)를 가지게 됩니다.

 - 간선의 수를 E, 정점의 수를 V

 

 크루스칼 알고리즘은 Union-Find를 함께 알아야 한다는 아쉬움이 있지만 간선의 개수가 적다면 프림보다 강력하게 동작할 수 있는 알고리즘이며 Union-Find를 전부 이해했다고 하면 쉽게 이해할 수 있는 알고리즘이었습니다.

 

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int v, e;
int a, b, c;
bool visit[10001];
vector<pair<int, int>> node[10001];

int main(){
    cin >> v >> e;
    long long answer = 0;

    for(int i = 0; i < e; i++){
        cin >> a >> b >> c;
        node[a].push_back(make_pair(b, c));
        node[b].push_back(make_pair(a, c));
    }

    priority_queue<pair<int, int>> q;

    q.push(make_pair(0, 1));

    while(!q.empty()){
        int curPos = q.top().second;
        int curCost = -q.top().first;
        q.pop();

        if(visit[curPos])
            continue;
        
        visit[curPos] = true;
        answer += curCost;

        for(int i = 0; i < node[curPos].size(); i++){
            int nextNode = node[curPos][i].first;
            int nextCost = node[curPos][i].second;

            q.push(make_pair(-nextCost, nextNode));
        }
    }

    cout << answer << '\n';
    
}

 프림 알고리즘은 자체만으로 동작을 하기 때문에 union find를 적는 크루스칼 알고리즘에 비해서 코드가 짧습니다. 다만 예시로 보는 백준의 1197 문제에서는 크루스칼 알고리즘이 더 시간이 적게 나온다는 걸 참고해야 합니다. 알고리즘의 순서는 아래와 같습니다.

 

1. 입력값을 전부 받은 뒤 우선순위 큐를 선언, 시작 지점을 정해서 큐에 첫 원소로 넣어줍니다.

    - 위 예시의 경우 1번 노드를 시작점으로 했으며 이때의 가중치는 0입니다.  (1번 노드에서 1번 가는 건 0이기 때문)

2. 큐의 top원소와 연결된 노드들을 탐색해 연결되어 있다면(이미 방문했다면) 넘어갑니다.

3. 아직 방문하지 않은 지점이라면 연결해준 뒤 새로 연결된 노드가 가진 간선들을 전부 우선순위 큐에 넣어줍니다.

    - 위 코드에서 우선순위 큐는 greater<pair<int, int>>를 넣지 않아 큰 값이 위에 오므로 (-)를 붙여 넣어줬습니다.

4. 큐에 더 이상 원소가 남지 않았다면 알고리즘을 종료합니다

    - 이 결과로 MST가 완성됩니다.

 

 위 과정을 그림으로 보면 위와 같습니다. 실제로 보면 시작 지점을 정하고 연결되는 지점들을 확장해나가는 방식입니다.

 

 

 처음 프림 알고리즘을 보았을 때 과연 '모든 노드가 방문되었는지 확인할 수 있는가?' 란 의문이 있었습니다. 크루스칼 알고리즘의 경우 parent배열과 union을 통해서 소속을 확인하는 작업이 있었는데 프림에는 이 작업이 없어서 생긴 의문이었습니다. 

 사실 잘 생각해보면 문제 자체에서 '간선이 없는 노드'가 있지 않는 한 MST는 무사히 만들어지게 됩니다. 그리고 저 가정은 사실상 MST를 만들 수 없다는 가정이므로 프림 알고리즘으로 무사히 MST를 만들 수 있다는 결론을 얻게 되었습니다.

 

 프림 알고리즘의 시간 복잡도는 힙을 사용하지 않고 배열을 사용하게 될 때 O(N^2)이 걸리게 됩니다. 이는 정점 N-1개만큼 루프를 돌게 되고 루프문 안의 동작(가장 작은 간선을 찾는 경우)이 N 번 돌아 O(N^2)의 시간복잡도를 가지게 되는 것이었습니다.

 그런데 위 코드의 경우 루프문 안의 최소 간선을 탐색하는 과정을 우선순위 큐(힙)으로 간소화를 했으므로 logN으로 줄어들게 됩니다. 그래서 O(NlogN)으로 최적화를 할 수 있었습니다. 정확히는 간선을 E, 노드의 수를 V 라고 했을 때 O(ElogV) 의 시간복잡도를 가지게 됩니다.

 

+ 피보나치 힙과 인접 리스트를 이용하면 E + VlogV까지 최적화를 할 수 있다고 합니다. 

 

---

<자료 출처>

- 크루스칼 알고리즘 이미지 : https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

Kruskal's algorithm - Wikipedia

- 프림 알고리즘 이미지 : https://en.wikipedia.org/wiki/Prim%27s_algorithm

Prim's algorithm - Wikipedia