[알고리즘 분류] - 최소 스패닝 트리

MST는 2가지 방법으로 구현할 수 있는데, 하나는 Prim이고, 다른 하나는 Kruskal 이다.

나는 대부분의 문제를 Kruskal 로 풀었는데, 주어진 문제들이 대부분 Sparse Graph 였기 때문이다. 

 

Kruskal는 모든 edge를 오름차순으로 정렬하고, 앞에서부터 (작은 순서대로) 판단을 하는데,

해당 edge의 양쪽 node가 같은 Group에 속해 있으면 연결하지 않고, 같은 Group에 속해있지 않으면 연결한다.

node의 갯수가 N개일 때, 연결한 edge가 총 N - 1 개가 되면 멈춘다. 

 

같은 Group인지를 판단할 때 Union-find 알고리즘을 그대로 사용한다. (매우 단순하다) 

edge를 정렬하는 단계에서 ElogE의 시간복잡도가 발생하고, 

edge를 선택하여 group을 판단하는 단계에서 logN (Union-find)

그걸 N번 반복하기 때문에 NlogN의 시간복잡도가 생긴다.