!!개인 공부용이기 때문에 틀린 내용이 있을 수도 있습니다!! 잘못된 내용이 있으면 언제든지 지적해 주세요.
Prim 알고리즘도 마찬가지로 MST를 구하기 위한 알고리즘이다.
Prim 알고리즘 역시 탐욕법을 사용하며, MST를 점점 확장시켜나가는 방법을 통해 최종적으로 우리가 원하는 MST를 구한다.
Prim 알고리즘에서는 먼저 시작 노드를 MST에 포함시키고 시작한다. 그 후 정점들을 확인하며 현재 인접한 정점들 중 가장 cost가 낮은 정점을 MST에 연결한다. 이 때, cost가 작더라도 cycle이 형성되는 경우는 연결하지 않는다. cycle 형성 여부는 union-find 알고리즘을 사용하여 알아낸다.
이같은 과정을 반복하며 모든 정점이 연결되면 알고리즘이 종료된다.
앞서 설명한 Kruskal 알고리즘의 경우 간선의 수에 따라 시간 복잡도가 결정되지만(간선을 cost순으로 정렬해야 하므로) Prim 알고리즘은 정점의 수에 따라 시간 복잡도가 결정된다. 따라서 간선의 수가 적다면(Sparse Graph) Kruskal을, 간선의 수가 많다면(Dense Graph) Prim을 사용하는 것이 좋다.
