최소 비용 신장 트리를 구하는 알고리즘이다.
크루스칼 알고리즘은 간선을 기준으로 그래프를 생성하여 최소 비용 신장 트리를 구한다.
프림 알고리즘은 임의의 정점을 선택하며 가중치가 적은 노드를 선택해서 연결해주고 가중치를 업데이트 하는 과정을 반복해준다.
크루스칼 알고리즘은 간선을 기준으로 그래프를 구하는 반면 프림 알고리즘은 정점을 기준으로 최소 비용 신장 트리를 구한다.
노드 0을 선택한다.
노드 0을 선택하고 연결된 모든 노드의 거리를 살펴본다. 직접 이어지지 않은 노드의 거리는 inf(무한대)가 된다.
따라서 0과 연결된 1, 2, 3에 각각 4, 6, 5가 할당된다. 그 후 거리가 가장 짧은 노드를 선택한다.
1번 노드의 거리가 4므로 거리가 가장 짧으니 1번 노드가 선택된다.
그 후 1번 노드와 연결된 노드들을 살펴본다.
4번 노드의 거리가 3이된다.
이렇게 0번과 1번노드가 연결되었는데 연결 된 이상 두 노드는 한개의 그룹으로 묶인다.
따라서 이 그룹과 연결된 모든 노드의 거리를 확인한다.
이후 이 가장 적은 거리를 가진 4번 노드를 선택한다.
노드 6의 거리가 1로 바뀌게된다. 또한 3번 노드는 5와 8 두가지의 거리가 있게되는데, 거리들중 가장 작은 거리가 선택된다.
다음 거리가 짧은 노드는 6이고 노드6을 선택한다.
노드6을 추가하게 되면 노드5의 거리가 6으로 바뀐다.
다음 거리가 짧은 노드3을 추가하게 되는데 가중치가 더 적은 방향의 간선을 추가해준다.
다음은 노드 2와 5가 남게 되는데 둘은 거리가 6이므로 같다. 둘 중 아무 정점을 추가해주고, 거리의 차이가 발생하지 않는다면 그대로 추가해준다.
이렇게 최소 비용 신장 트리가 만들어진다. 크루스컬 알고리즘은 간선별로 분해를 했다가 다시 합쳐지는 느낌이라면 프림 알고리즘은 그래프의 틀을 유지하며 최소 비용 신장 트리를 만들게 된다.
시간복잡도
O(n^2)