[그래프 알고리즘]프림 알고리즘(MST)

MST Minimum Spanning Tree

MST란 한 무향 그래프에서 특정 엣지들의 집합으로, 모든 노드들을 연결하면서, 가중치의 합이 제일 작은 엣지들의 집합이다.

MST는 트리이므로 엣지들의 개수는 노드의 개수에서 1을 뺀 수이다.

프림 알고리즘

프림 알고리즘은 한 노드에서 시작해, 주변 노드들을 MST에 포함시켜 나간다.

MST 에 포함될 다음 노드는, MST에 가장 작은 가중치로 연결된 노드이다.

모든 노드들이 MST에 포함될 때까지 반복한다.

구현

다익스트라 알고리즘과 유사하다.

MST에 연결된 노드들 중 가장 가중치가 작은 엣지에 연결된 노드를 선택한다.

선택 과정을 효율적으로 하기 위해 우선순위 큐를 이용한다.

MST는 결국 엣지들의 집합이므로, 노드를 선택할 때 고려된 엣지의 반대편 노드도 저장해야한다.