[알고리즘] 최소 스패닝 트리 - 프림(Prim) 알고리즘

스패닝 트리

간선의 수를 최소화 해서 모든 정점을 이용하는 트리이다.

N개의 정점이면 최소 N-1개의 간선으로 이루어져 있고 사이클이 발생하면 안된다.

간선의 수 뿐만 아니라 비용까지 계산해서 최단거리를 구하는 것이 최소 스패닝 트리이다.

 

프림(Prim) 알고리즘

프림 알고리즘도 크루스칼 알고리즘처럼 그리디 알고리즘으로 진행한다.

임의의 정점을 선택하고 T에 포함시킨 후 T에 포함된 노드와 포함되지 않은 노드 사이 

간선 중 가중치가 최소인 간선을 선택하고 도착 정점을 T에 포함시킨다.

 

https://www.weeklyps.com/entry/%ED%94%84%EB%A6%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Prims-algorithm

프림 알고리즘 ( Prim's algorithm )

프림 알고리즘 동작 과정에 대해 자세히 설명되어 있는 링크다.

구현하는 방법은 시간복잡도가 O(N^2)와 O(ElogN) 두가지 방법이 있다.

 

 

 

O(N^2)

O(N^2)는 선택한 노드들을 selected에 저장하고 선택한 노드들과 거리를 dist에 저장한다.

	dist[1] = 0;

처음에 임의의 정점을 선택한다. 1을 선택해보겠다.

		int now, minDist = INT_MAX;
		for (int j = 1; j <= V; j++)
		{
			if (!selected[j] && minDist > dist[j])
			{
				minDist = dist[j];
				now = j;
			}
		}

그리고 선택하지 않은 정점들 중 거리가 가장 가까운 정점을 now로 고르고 그 거리를 minDist에 저장한다.

dist들은 아직 1말고 모두 INT_MAX 아니냐고? 아니까 좀 기다려봐. 이러면 일단 정점 1이 선택되겠지? minDist는 0

 

		selected[now] = true;
		answer += dist[now];

		for (pair<int, int> elem : edges[now])
		{
			dist[elem.first] = min(dist[elem.first], elem.second);
		}

정점을 선택했다고 selected[now]를 true로 바꿔주고 최종 결과가 가중치에 dist[now]만큼 더해준다. 그리고

현재 선택한 정점을 기준으로 인접 정점들에 대하여 가중치 계산을 다시 한다. 그러면 이제 정점 하나를 선택한건데

정점을 모두 선택할 때까지 (정점개수)번 만큼 루프를 돌리면 되겠지?

 

 

 

O(ElogN) 

O(ElogN)는 dist배열 없이 최소 힙을 이용한다. 우선순위큐가 힙을 이용하기 때문에 오름차순 정렬하는 우선 순위 큐라고 봐도 무방하다. 이번에는 dist를 가중치 오름차순으로 정렬하는 우선순위큐라고 하자.

dist.push({0,1}); //가중치=0, 도착 정점=1

O(N^2)의 dist[1] = 0 역할을 한다.

 

int now=-1, min_dist = INT_MAX;
while(!dist.empty()){
    now = dist.top().second;
    if(!selected[now]){
        min_dist = dist.top().first;
        break;
    }
    dist.pop();
}

가중치가 작은 순서대로 뽑고 선택한 노드가 아니라면 min_dist에 저장해 선택한 정점중 가장 가까운 정점과 거리를 구한다. 가중치가 적은 순 정렬되어있기 때문에 선택하지 않은 노드라면 바로 break로 탈출해 효율적으로 구할 수 있다.

 

answer+=min_dist;
selected[now] = true;
for (pair<int, int> elem : edges[now])
{
	pq.push({ elem.first,elem.second });
}

마찬가지로 가중치를 추가하고 선택한다. 그리고 선택한 정점의 인접한 모든 간선을 dist 우선순위큐에 넣는다.

이제 정점 하나 선택한 것이므로 똑같이 이것을 정점개수만큼 반복하면 된다.