경계를 가로지르는 간선
트리에 들어온 정점들의 집합과 아직 들어오지 않은 정점들을 나눈다. 두 쪽을 잇는 간선 중 가장 가벼운 것을 골라 바깥 정점을 하나 추가한다. 양 끝이 이미 트리 안에 있는 간선은 새 정점을 추가하지 못한다.
한 단계의 예
현재 정점 집합이 {A,B}이고 바깥 정점 C,D로 나가는 후보가 AC=7, BC=2, BD=4라면 BC를 고른다. 그래프 전체에서 가장 싼 간선이 아니라 현재 경계의 후보 중에서 고른다는 점이 중요하다.
종료와 연결 조건
연결된 유한 그래프에서는 모든 정점이 들어오면 신장 트리를 얻는다. 연결되지 않은 그래프는 시작점이 속한 성분만으로 전체를 덮을 수 없다. 각 성분에서 다시 시작하는 방식으로 신장 숲을 구할 수 있다.
다익스트라와의 차이
두 알고리즘은 우선순위 큐를 사용할 수 있지만 비교하는 값이 다르다. 프림은 트리와 정점을 연결할 간선의 가중치를 비교하고 다익스트라는 출발점부터의 누적 거리 후보를 비교한다.
관련 문서
최소 신장 트리 / 신장 트리 / 가중 그래프 / 크루스칼 알고리즘 / 다익스트라 알고리즘 / 우선순위 큐 / 연결 성분