프림 알고리즘

[접기]

목차

  • 1. 개요
  • 2. 알고리즘


1. 개요


프림 알고리즘(Prim's algorithm)은 최소 스패닝 트리를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 힙을 이용해 구현할 경우 $ O(E\log{V}) $의 시간복잡도를 가진다. 그래프가 충분히 빽빽한 경우($ E = \Omega(V\log{V}) $)에는 피보나치 힙을 이용하여 훨씬 빠르게 구현할 수 있다. 이 방법은 시간복잡도가 $ O(E + V\log{V}) $까지 내려간다.

2. 알고리즘


프림 알고리즘은 다음과 같은 순서를 따른다.

분류 알고리즘