1. 개요
가중치가 있는 무방향 그래프에서 최소 비용 신장 트리 (MST, minimum spanning tree)를 구하는 그리디 알고리즘.우선순위 큐를 이용하여 구현하는 경우 [math(O((V+E)\log V))]의 시간복잡도를 가진다.
2. 알고리즘
다익스트라 알고리즘과 거의 동일한 알고리즘이다. 다익스트라 알고리즘의 평가 함수에서 현재 경로까지의 이동거리를 누적하지 않고 간선 가중치만을 이용한다면 프림 알고리즘이 된다. 다익스트라 알고리즘과 달리 음수의 가중치가 있는 경우에도 동작 가능하다.알고리즘은 기본적으로 다음 순서로 작동한다.
- 임의의 정점을 선택하여 하나의 정점을 갖는 최초의 트리를 구성한다.
- 트리에 포함된 정점과 트리에 포함되지 않은 정점 간의 간선 중 가장 작은 가중치를 가지는 간선을 선택하여 트리에 추가한다.
- 모든 정점이 트리에 포함될 때 까지 2를 반복한다.
이렇게 만들어진 트리가 최소 비용 신장 트리 문제의 최적해가 된다.