[알고리즘] 최소 스패닝 트리 - 프림 알고리즘

이전 글에 이어지는 글입니다.

[알고리즘] 최소 신장 트리 - 크루스칼 알고리즘과 Union Find, 백준 1197번 C++ 풀이

---

크루스칼 알고리즘에 이어서 프림 알고리즘을 알아보자. 

1. 임의의 정점을 선택해 최소 신장 트리에 추가
2. 최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선 중 비용이 가장 작은 것을 최소 신장 트리에 추가
3. 최소 신장 트리에 V-1 개의 간선이 추가될 때까지 2번 과정을 반복

방법 자체는 크루스칼과 유사하다. 다만, 정점을 기준으로 선택한다는 차이점이 있다. 알고리즘의 이해 자체는 어렵지 않은데 구현에서 문제가 생긴다. 우선순위 큐를 사용해서 알고리즘을 자세히 한 번 짜보자.

1. 임의의 정점을 선택해 최소 신장 트리에 추가, 해당 정점과 연결된 모든 간선을 우선순위 큐에 추가
2. 우선순위 큐에서 비용이 가장 작은 간선을 선택
3. 만약 해당 간선이 최소 신장 트리에 포함된 두 정점을 연결한다면 continue;
4. 해당 간선이 최소 신장 트리에 포함된 정점 u와 포함되지 않은 정점 v를 연결한다면 해당 간선과 정점 v를 최소 신장 트리에 추가 후 정점 v와 최소 신장 트리에 포함되지 않는 정점을 연결하는 모든 간선을 우선순위 큐에 추가
5. 최소 신장 트리에 V-1 개의 간선이 추가될 때 까지 2, 3, 4번 반복

int v, e;
vector<pair<int, int>> adj[10005];
bool chk[10005];
int cnt = 0;

priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;

chk[1] = true;
for (auto nxt : adj[1])
    pq.push({nxt.first, 1, nxt.second});

while(cnt < v-1){
    int cost, a, b;
    tie(cost, a, b) = pq.top();
    pq.pop();
    if(chk[b]) continue;
    cout << cost << ' ' << a << ' ' << b << '\n';
    chk[b] = 1;
    cnt++;
    for(auto nxt : adj[b]){
        if(!chk[nxt.second])
            pq.push({nxt.first, b, nxt.second});
    }
}

우선순위 큐에 익숙하다면 코드의 이해는 어렵지 않다. 알고리즘을 생각했던 대로 구현하면 된다. 

 

우선순위 큐에서 삽입, 삭제는 O(log E) 이므로 프림 알고리즘의 시간 복잡도는 O(E log E)가 된다. 크루스칼보다 빠르게 MST를 구할 수 있지만 구현이 꽤나 까다롭다. 둘 다 익혀두고 생각나는 대로 써먹는 방식이 좋을 것 같다.