MST _ Prim's Algorithm

Prim's 알고리즘은 시작 vertice에서부터 출발해서 MST 집합을 단계적으로 확장해 나가는 방법이다.

 

• Prim's 알고리즘의 동작

- 시작 단계에서 시작 vertice만이 MST 집합에 포함된다.

- 앞 단계에서 만들어진 MST 집합에 인접한 vertice들 중에서 최소 가중치를 가진 edge로 연결된 vertice를 선택하여 Tree를 확장해나간다. 즉, 가장 낮은 weight을 가장 먼저 선택한다.

- 위의 과정을 tree가 (n-1)개의 edge를 가질 때까지 반복한다.

 

여기서는 priority queue Q를 사용한다.

하나의 tree만을 유지한다는 것이 kruskal과 다른 점이다.

 

 

 

 

- Psuedocode

 

 

 

• Example of Prim's Algorithm

 

 

 

• Prim's Algorithm의 시간복잡도

주 반복문이 vertice의 수 n만큼 반복하고, 내부 반복분이 n번 반복한다 => O(n^2)

그래프에 간선이 많이 존재하는 Dense Graph (밀집 그래프)의 경우, Prim's 알고리즘이 적합하다.