크루스칼은 간선을 여기저기 막 추가하는 거고, 프림은 하나의 정점을 잡아서 스패닝 트리가 될 때까지 간선을 하나하나 추가한다.

(주의할 점!!!! : 무방향이지만, 양방향으로 넣어줘야 한다. 즉, E가 2배가 된다.)

트리와 각 정점을 연결하는 간선의 최소 가중치를 저장하는 배열 minWeight[ ]

각 정점이 실제 어떤 간선을 이용해 트리와 연결되었는지를 확인하기 위해, 사용하는 간선의 다른 한쪽 끝 정점을 parent[ ]에 유지

const int MAX_V = 100;
const int INF = (~0U >> 2);

// 정점의 개수
int V;
// 그래프의 인접 리스트. (연결된 정점 번호, 간선 가중치) 쌍을 담는다.
vector<pair<int,int>> adj[MAX_V];
// 주어진 그래프에 대해 최소 스패닝 트리에 포함된 간선의 목록을 selected에
// 저장하고, 가중치의 합을 반환한다.
int prim(vector<pair<int,int>>& selected)
{
	selected.clear();
	// 해당 정점이 트리에 포함되어 있나?
	vector<bool> added(V, false);
	// 트리에 인접한 간선 중 해당 정점에 닿는 최소 간선의 정보를 저장한다.
	vector<int> minWeight(V, INF), parent(V, -1);
	// 가중치의 합을 저장할 변수
	int ret = 0;
	// 0번 정점을 시작점: 항상 트리에 가장 먼저 추가한다.
	minWeight[0] = parent[0] = 0;
	for(int iter = 0; iter < V; ++iter)
	{
		// 다음에 트리에 추가할 정점 u를 찾는다.
		int u = -1;
		for (int v = 0; v < V; ++v)
		{
			if(!added[v] && (u == -1 || minWeight[u] > minWeight[v])) u = v;
		}
		// (parent[u], u)를 트리에 추가한다.
		if (parent[u] != u)
			selected.push_back(make_pair(parent[u], u));
		ret += minWeight[u];
		added[u] = true;
		// u에 인접한 간선 (u,v)들을 검사한다.
		for (int i = 0; i < adj[u].size(); ++i)
		{
			int v = adj[u][i].first, weight = adj[u][i].second;
			if (!added[v] && minWeight[v] > weight)
			{
				parent[v] = u;
				minWeight[v] = weight;
			}
		}
	}
	return ret;
}

시간 복잡도

추가할 새 정점을 찾는 작업 : O(|V|) // minWeight[ ]를 사용하기 때문에

모든 간선은 두 번씩만 검사되므로 전체 시간 복잡도는 O(|V|^2 + |E|)

즉 정점이 적고, 간선이 많은 밀집 그래프인 경우, 크루스칼보다 프림 알고리즘이 빠르다.

근데, 우선순위 큐를 사용해서 구현하면 O(|E|lg|V|) 가능.

구현해봤는데, 주의할 점은 무방향으로 데이터가 안 주어지고 단방향으로 주어졌을 경우에 양방향으로 두 개 다 넣어줘야 해서 E가 2배가 되면서 시간이 오래 걸렸다.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

const int MAX_V = 100000 + 1;
const int INF = (~0U >> 2);

priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> PQ;
bool Visited[MAX_V];
int Total = 0;
//int Best = 0;

int N, M;
vector<pair<int, int>> Road[MAX_V];
void Prim()
{
	PQ.push(make_pair(0, 1));

	for (int iter = 0; iter < N; ++iter)
	{
		bool bIsFind = false;
		int Cost, To;
		while (!bIsFind)
		{
			Cost = PQ.top().first;
			To = PQ.top().second;
			PQ.pop();

			if (!Visited[To]) bIsFind = true;
		}
		
		//Best = max(Best, Cost);

		Total += Cost;
		Visited[To] = true;

		for (int i = 0; i < Road[To].size(); ++i)
		{
			int Next = Road[To][i].first, NextCost = Road[To][i].second;
			
			if (!Visited[Next]) PQ.push(make_pair(NextCost, Next));
		}
	}
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);

	cin >> N >> M;
	for (int i = 0; i < M; ++i)
	{
		int From, To, Cost;
		cin >> From >> To >> Cost;

		Road[From].push_back(make_pair(To, Cost));
		Road[To].push_back(make_pair(From, Cost));
	}

	Prim();

	//cout << Total - Best;
	cout << Total;
	return 0;
}