Prim 알고리즘

Prim 알고리즘 동작 과정

1) 시작 노드를 빈 트리에 추가
2) 트리에 있는 노드와 없는 노드 사이 비용이 최소인 노드를 트리에 추가
3) 모든 노드가 포함될 때까지 반복

시작 노드를 1이라고 하자.
1) 노드 1을 트리에 추가하고 트리와 연결된 노드들 중 가장 비용이 작은 것을 선택한다.
그림에선 1-3, 1-2 중 1-3의 비용이 더 작으므로 3을 트리에 추가한다.

2) 1-3 트리와 연결된 노드들 중 가장 비용이 작은 것을 선택한다.
선택할 수 있는 것은 1-2, 2-3, 3-4이며 비용이 가장 작은 것은 2-3이므로 2를 트리에 추가한다.

3) 모든 edge에 대해 탐색 완료하면 종료