최소 비용 신장 트리 - 프림(Prim) 알고리즘

프림(Prim) 알고리즘

 

프림 알고리즘이란?

 

 - 최소 비용 신장 트리(MST)를 찾는 알고리즘

 

 - 시작 정점에서 출발하여 신장 트리를 확장하는 알고리즘

 

 - 시간 복잡도 : 인접 행렬 사용 시 O($V^2$)

                     우선 순위 큐, 인접리스트 사용 시 O(ElogV)

 

 - 간선의 숫자가 노드의 숫자보다 적은 경우 크루스칼을, 많은 경우 프림을 사용하면 좋다.

 

---

 

프림 알고리즘 실행 과정

 

 - 1. 시작 정점을 선택한다.

 

 - 2. 해당 정점과 연결 된 정점 중 선택되지 않은 간선들을 우선순위 큐에 넣는다.

 

 - 3. 우선순위 큐에서 값이 제일 작은 간선을 뽑아 연결한다.

 

 - 4. 2~3번 과정을 반복한다.

 

 

- 초기 상태(1을 시작 점을 설정)

 

 

 

- 1과 연결된 간선 중 가장 작은 값인 2를 선택하고, 1과 2를 연결한다.

 

 

- 2와 연결 된 간선 중 가장 작은 값인 1을 선택하고, 2와 3을 연결한다.

 

- 3과 연결된 간선 중 가장 작은 값인 5를 선택하고 3과 4를 연결해서 완성한다.

(가중치 4를 선택 안한 이유는 이미 정점 1과 3을 연결되어 있기 때문이다. )

 

---

프림 코드(C++)

#include <bits/stdc++.h>

using namespace std;

void prim(vector<vector<pair<int, int>>> v,int start)
{
	// 가중치, 정점
	priority_queue<pair<int, int>> pq;
	int sumWeight = 0;

	vector<bool> isVisit(v.size(), false);
	isVisit[start] = true;

	cout << start+1 << " 추가 " << endl;

	for (int i = 0; i < v[start].size(); i++)
	{
		pq.push({ -v[start][i].second,v[start][i].first });
	}

	while (!pq.empty())
	{
		int nowCost = pq.top().first;
		int nowNode = pq.top().second;
		pq.pop();
		if (isVisit[nowNode])
			continue;

		isVisit[nowNode] = true;
		sumWeight += -nowCost;

		cout << nowNode+1 << " 추가 " << endl;

		for (auto next : v[nowNode])
		{
			int nextCost = next.second;
			int nextNode = next.first;

			if (!isVisit[nextNode])
			{
				pq.push({ -nextCost,nextNode });
			}
		}
	}

	cout << " 최소 비용 : " << sumWeight << endl;
	
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<vector<pair<int, int>>> v(4, {});
	v[0].push_back({ 1,2 });
	v[0].push_back({ 2,4 });
	v[1].push_back({ 2,1 });
	v[0].push_back({ 3,6 });
	v[2].push_back({ 3,5 });
	v[1].push_back({ 3,7 });


	prim(v,0);


	return 0;
}

 

실행 결과