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;
}