127. Prim's Algorithm

프림 알고리즘(Prim's Algorithm)은 무향 그래프의 최소 스패닝 트리를 구하는 두 번째 알고리즘으로, 다음과 같은 방법으로 작동한다.

    1. 그래프에서 정점 하나를 임의로 골라서 $v$라고 한다.

    2. 연결하는 한쪽 정점이 $v$와 연결된 정점들의 집합에 포함되고 다른 정점은 집합에 포함되지 않는 간선들 중 가중치가 가장 작은 간선 하나를 선택하고 최소 스패닝 트리에 추가한다.

    3. 모든 정점이 $v$와 연결될 때까지 2번 과정을 반복한다.

 

이것도 설명이 짧아서 예시를 같이 살펴보면 편할 것이다. 앞에서 나온 그래프에서 정점 $\text{H}$가 $v$로 선택되었다면 다음과 같이 스패닝 트리가 만들어지게 된다.

먼저 정점 $\text{H}$와 연결된 간선 중 가중치가 가장 작은 간선이 최소 스패닝 트리에 추가된다.

이번에는 정점 $\text{F}$, $\text{H}$를 함께 확인한다. 이 그룹에 연결된 간선 중에서 가중치가 가장 작은 간선은 정점 $\text{F}$와 $\text{D}$를 연결하는 것이고, 이 간선을 선택한다.

다음으로 이 그룹과 연결된 간선 중 가중치가 가장 작은 간선은 정점 $\text{A}$와 $\text{D}$를 연결하는 것이고, 이 간선을 선택한다.

다음으로 정점 $\text{D}$와 $\text{E}$를 연결하는 간선과 정점 $\text{H}$와 $\text{I}$를 연결하는 간선이 차례로 선택된다.

다음으로 정점 $\text{E}$와 $\text{C}$를 연결하는 간선, 정점 $\text{I}$와 $\text{G}$를 연결하는 간선, 정점 $\text{A}$와 $\text{B}$를 연결하는 간선을 차례로 선택하면 알고리즘은 종료된다.

---

구현은 다음과 같다. 선택할 수 있는 간선을 우선순위 큐에 넣고 가중치가 작은 순서대로 확인하면서 최소 스패닝 트리에 추가하면 된다. 편의상 시작 정점 $v$는 $1$번 정점으로 고정한다. [샘플 코드]

#import<bits/stdc++.h>
using namespace std;
int vi[100005];
vector<pair<int, int>>e[100005], mst[100005];
priority_queue<pair<int, pair<int, int>>>Q;
int main()
{
    int m, n, x, y, z;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        e[x].push_back({y, z});
        e[y].push_back({x, z});
    }
    vi[1] = 1;
    for(auto &p: e[1])Q.push({-p.second, {1, p.first}});
    for(; Q.size(); )
    {
        x = Q.top().second.first;
        y = Q.top().second.second;
        z = -Q.top().first;
        Q.pop();
        if(!vi[y])swap(x, y);
        if(!vi[x])
        {
            mst[x].push_back({y, z});
            mst[y].push_back({x, z});
            vi[x] = 1;
            for(auto &p: e[x])Q.push({-p.second, {x, p.first}});
        }
    }
}

 

[연습문제]

 

BOJ 2887. 행성 터널 (Platinum V)

각각의 좌표를 기준으로 행성들을 정렬했을 때 인접한 위치에 있는 행성들 사이에 터널을 놓는 경우만 고려하면 된다. 가능성이 있는 터널을 간선으로 간주하여 최소 스패닝 트리를 구한다.