프림 알고리즘

https://youtu.be/4wA3bncb64E?si=vHf57OGLXMJMD6T9

설명

1. 임의의 정점 선택해 최소 신장 트리에 추가
2. 최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선 중 비용이 가장 작은 것을 최소 신장 트리에 추가
3. 최소 신장 트리에 V-1 개의 간선이 추가될 때 까지 2번 과정 반복 우선순위 큐를 활용한 구현. 크루스칼 알고리즘보다 구현이 좀 더 어렵다.

프림 알고리즘 구체적

1. 임의 정점 선택하여 최소 신장 트리에 추가, 해당 정점과 연결된 모든 간선을 우선순위 큐에 추가
2. 우선순위 큐에서 비용이 가장 작은 간선 선택
3. 만약 해당 간선이 최소 신장 트리에 포함된 두 정점을 연결한다면 아무 것도 안하고 넘어감, 해당 간선이 최소 신장 트리에 연결된 u와 포함되지 않은 정점 v를 연결한다면 해당 간성과 정점 v를 최소 신장 트리에 추가한 뒤 v와 최소 신장 트리에 포함되지 않는 정점 연결하는 모든 간선을 우선순위 큐에 추가
4. 최소 신장 트리에 V-1개의 간선 추가될 때 까지 2,3 과정 반복

O(ElogE)

boj 1368