[알고리즘 공부] 프림 알고리즘 Prim's Algorithm

프림 알고리즘이란?

최소 신장 트리 (Minimum Spanning Tree, MST) 구현에 사용되는 알고리즘으로 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장하는 기법이다.

 

프림 알고리즘의 시퀀스

1. 시작할 정점을 MST집합에 넣는다.
2. MST집합에 속한 정점들과 인접한 정점들 중 가장 낮은 가중치의 간선과 연결된 정점을 MST집합에 넣는다.
3. 2번과정을 MST집합의 원소 개수가 그래프 정점의 갯수가 될 때까지 반복한다.
4. 만들어진 MST집합의 가중치를 다 더해서 MST Cost 산출.

프림 알고리즘으로 MST 구하기

크루스칼 알고리즘 vs 프림 알고리즘

크루스칼 알고리즘 : Kruskal's Algorithm	프림 알고리즘 : Prim's Algorithm
그래프의 최소 가중치 간선들을 정렬된 순서로 추가하여 MST 구성	그래프의 아무 정점부터 시작하여 MST 구성
통상적으로 O(E logV)의 시간복잡도	통상적으로 O(E + V logV)의 시간복잡도
주로 간선의 수가 적은 희소그래프_Sparse Graph에 유리	주로 간선의 수가 많은 밀집그래프_Dense Graph에 유리