[알고리즘] Prim`s algorithm. MST 구하는 2번째 방법. 프림

반갑습니다.

이번엔 O(ElogV) 시간복잡도를 가지는 Prim알고리즘에 대해서 알아보겠습니다.

​

이건 음.. heap을 알아야 하는데, 힙구조를 가지는 priority_queue를 사용할 수 있으면 좋습니다.

없으면 kruskal이 구현하기 더 낫습니다.

​

​

Kruskal VS Prim

결과부터 말하면 Edge가 많으면 Prim, Edge가 적으면 Kruskal이 좀 더 좋습니다. (이론상)

​

Kruskal은 sort과정에 O(ElogE)이 피할 수 없기에 E에 영향을 받고, Prim은 O(ElogV)입니다. 이미 방문된 지점은 다시 방문되지 않기에 pq의 push나 pop과정이 없어서 그렇습니다. 근데 MST를 찾는다는건 기본적으로 V < E니까 쓰겠죠...?

근데 그냥 편한대로 합시다.

​

두개의 차이는, kruskal은 weight가 낮은 지점부터 그냥 시작해서 MST가 이상한 순서로 만들어지는것처럼 보입니다.(답은 결국 같게 나오지만)

Prim은 특정 Source를 잡고 시작해서 좀 뭐랄까.. src에서 뻗어나가는 느낌으로 됩니다.

​

Prim을 기억에 남기기 위해서 하는것이기 때문에 자세한 설명은 다른곳을 보시길 바랍니다.

한국은 barkingDog님 블로그, 외국은 유튜브 TECH DOSE 강추요 ㅎ;

​

Prim 알고리즘 순서.

이것도 마찬가지로 무방향 그래프에 대해서 구하게 됩니다.

​

시작점을 src라고 하겠습니다.

1. src의 edge들에 대해서 모두 heap에 넣습니다. src를 방문처리 합니다(이 node는 방문했다고 처리)

2. 가장 작은 edge가 나오게 됩니다. 그 edge를 연결한 node에 대해서도 방문처리를 합니다 ( u,v가 있으면 v를 방문처리 합니다)

3. 2에서 방문처리한 node에 대해서 다시 모든 edge를 heap에 넣습니다.

4. 2~3을 모든 V에 대해서 수행합니다. if(cnt == V-1) break; 이런식으로 하셔도 됩니다.

​

#include<bits/stdc++.h>
using namespace std;
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;
#define VERTEX 10005
#define EDGE 100005
vector<pii> vt[VERTEX];
bool visited[VERTEX];
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int u,v,w,V,E;
	int cnt = 0;
	int ans = 0;
	priority_queue<tiii,vector<tiii>,greater<tiii> > pq;
	cin >> V >> E;
	for(int i = 0; i < E; i++)
	{
		cin >> u >> v >> w;
		vt[u].push_back({v,w});
		vt[v].push_back({u,w});
// 양방향으로 값을 받음
	}

//임의의 한 점의 edge를 다 넣음
	for(auto i : vt[1]){
		pq.push({i.second,1,i.first});
	}
	visited[1] = true;
//방문처리

	while(!pq.empty())
	{
		tie(w,u,v) = pq.top(); pq.pop();
//vertex를 빼서 방문확인
		if(visited[v]) continue;
		visited[v] = true;
		cnt++;
		ans += w;
// u v가 연결되어있다고 가정할때 v에 대해서 또 새로운 간선 찾음
		for(auto i : vt[v])
		{
			if(!visited[i.first]){
				pq.push({i.second,v,i.first});
			}
		}
		if( cnt == V-1 ) break;
	}
	cout << ans;
	return 0;
}

방문처리가 이상하게 되는것을 주의해야 합니다.

예를들면 arr[1]을 pq.pop을 하고나서 방문처리를 한다던가 이렇게 하면 문제가 생깁니다. (맨 마지막 vertex가 방문이 되지 않아서 답이 이상하게 나옵니다.)

​

시간복잡도를 보면

while만 보면

for문 자체는 모든 E에 대해서 돌아가지만, 실제로 pq에 삽입이 일어나는건 V에 대해서만 일어나는걸 볼 수 있습니다.

따라서 O(E * logV) 가 되게 됩니다.

​

감사용!!

맞게 했는지는 여기서 체크해보시면 됩니다.

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리