프림 알고리즘

프림 알고리즘(Prim's algorithm)

최소 신장 트리를 구하는 알고리즘 중 하나
프림 알고리즘 눈으로 보기

최소 신장 트리(minimum spanning tree)

가중치 그래프에서 모든 정점을 연결하는 간선의 가중치 합이 최소인 트리

결국,

시작 정점에서부터 출발하여, 해당 정점과 연결된 간선 중에 가장 가중치가 작은 간선을 선택하며, 그 간선으로 연결된 정점을 트리에 포함시키는 최소 신장 트리를 구하는 방식이다.

How?

1. 임의의 정점을 시작 정점으로 선택하고, 해당 정점과 연결된 간선을 모두 우선순위 큐에 삽입한다.
2. 우선순위 큐에서 가중치가 가장 작은 간선을 선택하고, 해당 간선으로 연결된 정점을 트리에 포함시킨다.
3. 포함된 정점과 연결된 간선을 모두 우선순위 큐에서 제거한다.
4. 우선순위 큐가 빌 때까지 2~3 과정을 반복한다.

간선의 개수에 따른 속도의 차이

우선순위 큐를 사용하여 간선을 선택하기 때문에, 간선의 개수가 많아지면 실행 시간이 길어지고,간선의 개수가 적을 때는 크루스칼 알고리즘보다 실행 속도가 빨라진다

시간 복잡도

O(E log V)의 시간 복잡도를 가지는데, V는 정점의 개수, E는 간선의 개수이다.