크래프톤 정글 주제별 탐구 -프림 알고리즘-

정의

프림 알고리즘(Prim’s Algorithm)이란, MST를 구하기 위해 사용되는 알고리즘이다.

특징

프림 알고리즘의 경우, 다익스트라 알고리즘과 거이 유사한 알고리즘의 형태를 보인다. 다익스트라 알고리즘의 평가 함수에서 현재 경로까지의 이동거리를 누적하지 않고, 간선 가중치만을 이용한다면 이 프림 알고리즘이 되는 것이다. 또한, 다익스트라 알고리즘과는 다르게, 음수의 가중치가 있는 경우에도 구할 수 있다.

작동 방식

프림 알고리즘의 작동방식을 간단히 알아보자.

1. 임의의 정점을 선택하여, 비어있는 T(Tree)에 포함시킨다.
2. T에 있는 노드와 T에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.
3. 찾은 간선이 연결하는 두 노드 중, T에 없던 노드를 T에 포함시킨다.
4. 모든 노드가 T에 포함될때까지 2~3을 반복한다.