프림(prim) 알고리즘

 최소 신장 트리(Minimum Spanning Tree, MST) 구현에 사용되는 알고리즘이다. 최소 신장 트리란 그래프에서 모든 정점을 최소 비용으로 연결하는 트리이다.

 프림 알고리즘 다음 과정을 따른다.

 

1. 시작 정점을 하나 정함.

2. 연결 가능한 간선들 중 가장 비용이 낮은 간선을 선택

3. 해당 간선이 연결하는 정점이 아직 MST에 포함되지 않았다면 추가

4. 1~3을 모든 정점이 연결될 때까지 반복

 

프림은 O(ElogV)의 시간 복잡도를 가지며, priority_queue를 사용하여 구현할 수 있다.

(MST 구현에 사용되는 다른 알고리즘인 크루스칼은 O(ElogE)이다. 따라서 간선이 많은 경우는 프림이 유리하다.)

 

int mst() {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	int totalCost = 0;
	int count = 0;

	pq.push({ 0, 1 });

	while (!pq.empty()) {
		int curr = pq.top().second;
		int currCost = pq.top().first;
		pq.pop();

		if (visited[curr]) continue;

		visited[curr] = true;
		totalCost += currCost;
		count++;

		if (count == V) break;

		for (auto i : graph[curr]) {
			int next = i.first;
			int nextCost = i.second;
			if (!visited[next]) pq.push({ nextCost, next });
		}
	}
	return totalCost;
}