• 대표적인 최소 신장 트리 알고리즘

• 그리디 알고리즘으로 분류

• 최소 신장 트리의 특징

동작 과정

1. 임의의 정점을 선택한다.
2. 선택한 정점으로부터 가장 낮은 가중치를 갖는 정점을 선택한다.
3. n-1 번 반복한다.

시간 복잡도

프림 알고리즘의 시간 복잡도는 최소 우선순위 큐를 어떻게 구현하느냐에 따라 다르다.

피보나치 힙 : O(E+VlogV)

이진힙 : O(ElogV)

행렬 : O(V^2)

일반화된 시간 복잡도 수식