Prim’s Algorithm

프림 알고리즘 (Prim’s Algorithm)

크루스칼 알고리즘이 엣지를 하나하나 추가하는 방식이였다면
이 알고리즘은 버텍스를 추가해나가는 알고리즘이다.
자기한테 연결되어있는 엣지 중에
weight 가 가장 작은 놈으로만 가서
해당 버텍스를 추가한다.

1. 처음에 빈 트리 공간을 마련한다. 이를 T라 하자.
2. T에 있는 버텍스들에 근접한 모든 버텍스들을 찾는다.
3. T에 속한 버텍스와 T에 속하지 않는 버텍스를 연결하는 엣지 중
   가장 가중치가 적은 엣지를 고른다.
4. 만약 엣지가 사이클을 형성하지 않는다면 그 버텍스를 T에 추가한다.
5. 모든 버텍스들이 T에 담길 때까지 이 과정을 반복한다.

추가하려는 버텍스와 연결된 엣지 중에서
다른 한 끝의 버텍스가 이미 추가된 버텍스가 아니라면
그 엣지는 후보 엣지이다.
사이클을 형성하지 않는 것이다.
이렇게 되면 항상 새로운 버텍스만 추가되게 된다.

이들 중 최소 가중치를 가지는 엣지를 따라가
그 버텍스를 추가하는 것이다.

그리고 그렇게 선택된 엣지들이
바로 최소 신장 트리이다.

시간 복잡도

사이클을 분석하는 과정은
상수 개의 버텍스와 엣지를 분석하므로 (인접 리스트라는 가정 하)
O(1) 이다.

이걸 V 번 반복할 것이므로 버텍스의 추가는 O(V) 이고
거기에 달린 엣지들 중 최소값 찾는 것은 O(ElogE) 인데
후자가 더 크므로
시간 복잡도는 O(ElogE) 이다.

코드

백문이불여일타

GitHub