프림 알고리즘

위키백과 ― 우리 모두의 백과사전.

프림 알고리즘(Prim's algorithm)은 가중치가 있는 연결된 무향 그래프의 모든 꼭지점을 포함하면서 각 변의 비용의 핪이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 걸침 나무를 찾는 알고리즘이다. 간선의 개수를 E, 정점의 개수를 V라고 하면 이 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때를 기준으로 O(E log V)의 시간복잡도를 가진다. 그래프가 충분히 빽빽한 경우(E = Ω(Vlog V))에는 피보나치 힙을 이용하여 훨씬 빠르게 할 수 있다. 이 방법은 복잡도가 O(E + V log V)까지 떨어진다.

[편집] 알고리즘

프림 알고리즘은 아래의 순서대로 작동한다:

  • 그래프에서 하나의 꼭지점을 선택하여 트리를 만든다.
  • 그래프의 모든 변이 들어 있는 집합을 만든다.
  • 모든 꼭지점이 트리에 포함되어 있지 않은 동안
    • 트리와 연결된 변 중 트리 내의 두 꼭지점을 연결하지 않는 가장 가중치가 작은 변을 트리에 추가한다.

알고리즘이 종료됐을 때 만들어진 트리는 최소 비용 트리가 된다.

[편집] 같이보기