프림 알고리즘은 현재 만든 트리와 바깥 정점을 잇는 가장 가벼운 간선을 반복 선택하는 최소 신장 트리 알고리즘이다.
원리
하나의 시작 정점에서 트리를 확장한다. 바깥 정점마다 트리에 연결하는 최소 간선 비용을 관리하고 우선순위 큐로 선택할 수 있다.
그래프 알고리즘 |
|---|
너비 우선 탐색 · 깊이 우선 탐색 · 다익스트라 알고리즘 · 벨만 포드 알고리즘 · 플로이드 워셜 알고리즘 |
예시
A에서 시작했다면 A에서 나가는 가장 가벼운 간선을 고르고, 다음에는 이미 포함된 정점 전체에서 바깥으로 나가는 간선을 비교한다.
주의할 점
다익스트라의 키는 시작점부터의 누적 거리지만 프림의 키는 트리에 붙이는 간선 비용이다. 겉모양이 비슷해도 목적과 갱신식이 다르다.