가중치가 있는 무방향 그래프에서 minimum spanning tree (MST) 를 구하는 알고리즘이다. MST 는 모든 정점을 사이클 없이 연결하면서 간선 가중치 합이 가장 작은 부분 그래프를 말한다. 도시를 전부 잇는 도로망을 최소 비용으로 까는 문제가 이 모양이다.
동작
정점 하나에서 시작해, 이미 만든 트리에 붙일 수 있는 간선 중 가장 싼 것을 하나씩 골라 트리를 키운다.
- 아무 정점이나 하나 골라 트리에 넣는다
- 트리 안의 정점과 트리 밖의 정점을 잇는 간선 중 가중치가 가장 작은 것을 고른다
- 그 간선과 반대편 정점을 트리에 넣는다
- 모든 정점이 들어갈 때까지 2–3 을 반복한다
3번에서 트리 밖 정점만 넣으므로 사이클이 생기지 않는다. 2번의 “가장 작은 것” 은 Heap 을 우선순위 큐로 써서 꺼내며, 이때 다.
다른 알고리즘과의 관계
greedy algorithm 이고, 각 단계의 국소적 최선이 전체 최적으로 이어지는 것이 증명돼 있다. 근거는 cut property 다 — 정점 집합을 둘로 가르는 어떤 방식에 대해서도, 그 경계를 넘는 간선 중 가장 싼 것은 어떤 MST 에 반드시 포함된다.
Dijkstra algorithm 과 진행 방식이 거의 같지만 비교하는 값이 다르다. Dijkstra 는 출발점으로부터의 누적 거리를 보고, Prim 은 트리에 붙이는 간선 하나의 가중치만 본다. 그래서 Prim 의 결과는 최단 경로 트리가 아니다.
MST 를 구하는 다른 방법인 Kruskal 은 간선을 가중치 순으로 정렬해 놓고 사이클이 안 생기는 것만 골라 담는다. 간선이 적은 희소 그래프에서는 Kruskal 이, 간선이 많은 그래프에서는 Prim 이 유리한 편이다.