프림 알고리즘

최소 스패닝 트리를 구하는 알고리즘 중 하나. 최소 스패닝 트리는 사이클이 없는 트리의 형태로 만들고, 간선의 가중치가 최소가 되는 형태를 말한다

프림 알고리즘은 총 4가지의 단계로 구성된다

1. 시작 정점을 잡고 큐에 넣는다

2. 큐에서 pop하고, 해당 정점과 간선을 조사하면서 최소값을 고른다

3. 선택한 간선은 큐에 넣는다

4. 2번을 반복

 

최솟값을 가지는 간선을 찾기 위해서 매번 정렬을 해야기 때문에 힙으로 구성된 우선순위 큐를 사용하는 것이 시간복잡도에서 뛰어나게 된다

 

모든 정점에 대해서 살펴봐야 하므로 O(V)

간선을 탐색하는데 힙을 사용하므로 O(logE), 따라서 프림 알고리즘의 시간 복잡도는 O(VlogE)