최소 스패닝 트리(MST) : 프림 알고리즘 (Prim's Algorithm)

• 가중치가 있는 연결된 무향 그래프에서 최소 스패닝 트리(Minimum Spanning Tree, MST)를 수하는 알고리즘이다.
• 이진 힙으로 구현하였을 때 $ O(ElogV) $의 시간 복잡도를 가진다. (V : 정점(vertex), E : 간선(edge))
• 그래프의 간선이 충분히 많을 경우 ($E = \Omega(VlogV) $), 피보나치 힙으로 구현하면 시간이 단축된 $ O(E + VlogV) $의 시간 복잡도를 가진다. (V : 정점(vertex), E : 간선(edge))

 

알고리즘

  1. 간선을 담을 빈 집합을 준비한다.

  2. 그래프에서 임의의 한 정점을 선택하여 트리에 추가한다.

  3. 그 정점에 연결된 모든 간선을 집합에 삽입한다.

  4. 집합에서 가중치가 가장 낮은 간선을 선택한다.

      4-1. 선택된 간선의 양 끝 정점이 모두 트리에 추가되어 있다면 그다음 간선을 선택한다.

      4-2. 선택된 간선의 양 끝 정점 한 정점이 트리에 없다면 그 정점을 트리에 추가한다.

  5. 3~4번 과정을 모든 정점이 트리에 추가될 때까지 반복해 준다.

 

그림 예시

위의 그래프를 예시로 동작과정을 살펴보자.

 

먼저 그래프에서 임의의 정점을 골라준다.
예시에서는 1번 정점을 임의의 정점으로 선택했다.

그 다음 1번 정점과 연결된 모든 간선들을 집합에 추가해 준다.

 

집합에 있는 간선 중 가중치가 가장 낮은 간선은 1번 정점과 3번 정점을 잇는 간선이다.
간선의 양 끝 정점 중 3번 정점이 트리에 없으므로 추가해 준다.

그다음 3번 정점과 연결된 간선을 집합에 추가해 준다.

 

집합에 있는 간선 중 가장 낮은 간선은 3번 정점과 5번 정점을 잇는 간선이다.
간선의 양 끝 정점 중 5번 정점은 트리에 없으므로 추가해 준다.
그다음으로 5번 정점과 연결된 간선을 집합에 추가해 준다.

위의 3번 정점과 5번 정점을 트리에 추가하는 과정과 동일하게 6번 정점도 트리에 추가하고 6번 정점에 연결된 간선을 집합에 추가해 준다.

 

집합에 있는 간선 중 가장 낮은 가중치를 가진 간선은 정점 5번과 정점 6번을 잇는 간선이지만,

두 정점 모두 이미 트리에 추가되어 있으므로 넘어간다.

 

그다음 과정으로는 집합에 있는 간선 중 가작 낮은 가중치를 가진 정점 4번과 정점 6번을 잇는 간선이 선택되고,

기존의 트리에 없는 4번 정점을 트리에 추가해 주고 4번 정점과 연결된 간선들을 집합에 추가한다.

 

위의 과정과 동일하게 2번 정점을 트리에 추가하고, 2번 정점과 연결된 간선을 집합에 추가한다.

위의 과정과 동일하게 7번 정점을 트리에 추가하고, 7번 정점과 연결된 간선을 집합에 추가한다.

모든 정점이 트리에 추가되었으므로 과정은 끝나고 다음과 같은 트리가 남게 된다.

 

 

코드 구현

#include <iostream>
#include <vector>
#include <queue>
#define PII pair<int, int>
using namespace std;

bool visited[10001];
vector<PII> edge[10001];
long long ans = 0;

void prim(){
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, 1});

    int cost, idx, next_cost, next_idx;
    while(!pq.empty()){
        cost = pq.top().first;
        idx = pq.top().second;
        pq.pop();

        if(visited[idx]) continue;
        visited[idx] = true;

        ans += cost;

        for(int i=0; i<edge[idx].size(); i++){
            next_cost = edge[idx][i].first;
            next_idx = edge[idx][i].second;

            if(visited[next_idx]) continue;

            pq.push({next_cost, next_idx});
        }
    }
}

int main(){
    int V, E; cin >> V >> E;
    int v1, v2, cost;
    for(int i=0; i<E; i++){
        cin >> v1 >> v2 >> cost;
        edge[v1].push_back({cost, v2});
        edge[v2].push_back({cost, v1});
    }

    prim();

    cout << "최소 스패닝 트리의 가중치 합은 " << ans << "입니다.";
}

입력

7 9
1 2 20
1 3 4
1 6 9
2 4 10
3 5 8
4 6 15
4 7 16
5 6 13
6 7 18

출력

최소 스패닝 트리의 가중치 합은 62입니다.