최소신장트리 MST: Prim's algorithm

프림알고리즘은 최소신장트리, MST(minimum spanning tree)를 찾는 알고리즘이다.

최소신장트리 는 무향그래프의 모든 정점을 잇는 신장트리 중 그 가중치의 합이 최소인 그래프이다.

알고리즘은 다음과 같다.

• (1) 시작할 정점을 선택한다. 아무 정점이나 선택해도 된다.
• (2) 선택한 정점에서 갈 수 있는 다른 정점 중 가장 가중치가 작은 정점을 선택해 잇는다.
• (3) 이어진 정점들에서 갈 수 있는 정점 중 가장 가중치가 작은 정점을 선택해 잇는다.
• (4) 모든 정점을 선택할 때 까지 (3)과정을 계속 반복

이어진 정점이라고 표기했는데 선택한 정점이 최소신장트리에 포함되는 것이며,
지금까지 선택한 모든 정점들에서 선택하지 않은 정점까지의 가중치가 가장 작은 것 을 선택하는 것이다.
작은 것들만 선택하는 것에서 알 수 있듯 그리디 알고리즘이다.

구현은 다익스트라의 구현과 마찬가지로 우선순위큐를 사용할 것이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
priority_queue<pair<ll, int>> PQ;

vector<pair<int, ll>> vertex[10001];
//vertex[i] : 정점i에서 갈 수 있는 다른 정점과 가중치를 원소로 가짐

bool vist[10001];

int main()
{
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int V, E, A, B; 
    ll C, ans = 0;
    cin >> V >> E;
    for (int i = 0; i < E; i++)
    {
        cin >> A >> B >> C;
        vertex[A].push_back(make_pair(B, C));
        vertex[B].push_back(make_pair(A, C));
    }
    //아무데서나 시작!
    PQ.push(make_pair(0, 1));

    while (!PQ.empty())
    {
        int Ver = PQ.top().second;
        int Cost = -PQ.top().first;
        PQ.pop();
        if (vist[Ver]) continue;//MST에 추가돼있는거면 패스
        vist[Ver] = true; //선택한 정점은 방문처리를 해줌
        ans += Cost; //가중치 더해줌
        for (int i = 0; i < vertex[Ver].size(); i++)
        {
            //연결된 정점들 중 MST에 추가돼있는거면 패스
            if (vist[vertex[Ver][i].first]) continue; 

            //Ver에서 갈 수 있는 다른 정점과 그 가중치를 큐에 추가
            PQ.push(make_pair(-vertex[Ver][i].second, vertex[Ver][i].first)); 
        }
    }

    return 0;
}