최소 스패닝 트리 (MST) - 프림 알고리즘

 

최단거리 알고리즘에는 우리가 익히 잘 아는 다익스트라 알고리즘, BFS가 대표적이다.

그러나 이 두개의 알고리즘은 모든 정점을 지나지 않고 무조건 최단거리를 찾는다. 

 

그래서 모든 정점을 방문해야하는 문제를 해결할 수 없다. 때문에 MST 최소 스패닝 트리가 필요하다.

그래프에서 모든 정점을 지나는 트리를 그린다는 의미이다.

 

1. 프림 알고리즘

 

프림 알고리즘은 "정점" 을 아무거나 한 개 선택한다. 그리고 정점의 인접 정점들 중 가장 거리가 가까운 정점으로 이동한다. 그리고 지금까지 지나온 정점들 중 가장 가까운 곳으로 간다. 그림을 통해 이해하자.

 

자세히 설명해보면,

스탭1:  아무 정점이나 넣는다. 보통 1을 넣는다. 그리고 1에서 가장 가까운 곳으로 이동하면서 dist 배열을 업데이트한다.

스탭2: 현재 지나온 정점들 1, 2 와 가장 가까운 인접 노드를 탐색한다. 여기서 후보는 3 ,4, 5인데, 2에서 3으로가는 길이 0이므로 여기로 간다. 그리고 dist를 업데이트한다.

 

스탭3, 4: 스탭2와 같다. 그리고 마지막 노드는 방문하지 않아도 된다. 어차피 모두 업데이트 되었으니까. 

 

여기서 점화식을 도출해보면

 

dist[next] = min(dist[next], dist[now] + cost)

 

공식을 얻을 수 있고, 이 공식은 다익스트라와 유사하다. 프림도 결국 greedy 하지만 dp의 요소를 가지고 있다. 결국은 메모이제이션한 것을 사용하기 때문이다.

 

코드로 구현해보면 다음과 같다.

 

for (int i = 1; i <= N - 1; i++) {
				long long min_cost = INF;
				int next_node = 0;
				for (int j = 1; j <= N; j++) {
					if (visited[j]) continue;
					if (PrimsDist[j] < min_cost) {
						min_cost = PrimsDist[j];
						next_node = j;
					}
				}

				visited[next_node] = true;
				answer += min_cost;
                for (int j = 0; j < nodes[next_node].size(); j++) {
					int next = nodes[next_node][j].first;
					long long dist = nodes[next_node][j].second;

					if (visited[next]) continue;
					if (PrimsDist[next] > dist)	PrimsDist[next] = dist;
				}
			}

 

 

위에서 살펴봤듯, 이 과정은 N - 1번의 과정이 필요하다. 그러므로 N  - 1번 반복을 걸어주고

첫번째 반복문에서 다음 노드를 찾는다. 지금까지 방문했던 노드들을 제외하고 인접 노드들 중 비용이 낮은 곳을 찾는다. 

그리고 다음 반복문에서 찾은 노드로 이동 후 찾은 노드의 인접 노드들의 dist 배열을 업데이트한다.

 

Prim 알고리즘의 시간복잡도는 O(N^2)으로 N이 크면 쓰기 어렵겠지만, 최소 스패닝 트리 문제가 출제된다면 충분히 정해가 될 정도의 사이즈가 주어질 것이라 꼭 알고 있어야한다.