[알고리즘] Prim 알고리즘

개념

임의의 시작 노드에서부터 출발해 인접한 노드를 추가함으로써 모든 노드를 잇는 최소 비용을 구하는 알고리즘

과정

① 시작 노드를 MST 집합에 포함
② 앞 단계에서 만들어진 MST 집합에 인접한 노드들 중 최소 가중치의 간선으로 연결된 노드를 선택해 트리 확장
③ 위 과정을 트리가 (노드 개수 - 1) 개의 간선을 가질 때까지 반복

① 그래프 내 모든 노드들에 대해 key값을 무한대로, 시작 노드만 0으로 둔다.
② 시작 노드의 인접한 간선 중 최소값을 갖는 간선을 연결하고, 이 간선이 포함한 노드 u를 MST 집합에 포함시킨다.
③ u와, u의 인접 노드 v를 잇는 간선의 가중치가 노드 v의 key값보다 작은 경우 key값을 가중치로 update한다.

인접 노드를 계속 탐색하면서 최소 가중치를 찾는 알고리즘이기 때문에 한 노드를 여러번 방문할 수도 있다.
적은 간선을 갖는 희소 그래프의 경우 Kruskal 알고리즘이 유리하고 많은 간선을 갖는 밀집 그래프의 경우 Prim 알고리즘이 유리하다.