크루스칼 알고리즘(Kruskal's Algorithm) - 최소 신장 트리(Minimum Spanning Tree)

1. 개념

크루스칼 알고리즘은 최소 신장 트리를 찾는 알고리즘이다. 

최소 신장 트리는 무향 연결 G에서 간선의 가중치의 합이 최소인 신장 트리이다.

간선의 개수 E, 정점의 개수 V 일때 O(ElogV)의 시간복잡도를 가지는 알고리즘이다.

2. 구현

    1) V개의 정점, E개의 간선을 가진 가중 그래프 G에서 모든 간선을 오름차순으로 정렬한다.

    2) 정렬된 간선 목록에서 처음부터 마지막까지 아래의 과정을 반복한다.

      - 간선 목록에서 하나를 꺼내 해당 간선의 두 정점이 연결되어 있는지 확인한다.

      - 연결되어있지 않다면 두 정점을 연결한다.

구현할 때 팁은 오름차순 정리는 '우선순위 큐'를 사용하고, 두 정점의 연결 확인은 'Union-find'를 사용하는 것이다.

또한, cnt 변수를 따로 주어서 정점이 하나씩 추가될 때마다 cnt를 증가시켜 cnt가 정점의 수와 동일할 때

2) 과정을 중단시켜 불필요한 과정을 줄일 수 있다.

[크루스칼 알고리즘 예제 : http://gyutts.tistory.com/114?category=755806]