크러스컬 알고리즘(KruskalMST)

□ 크러스컬 알고리즘은 최소비용 생성나무(spanning tree 스패닝 트리)를 찾는 알고리즘이다. 

(생성나무란 그래프 이론에서 모든 꼭짓점을 포함하는 부분 나무이다.)

크러스컬의 알고리즘은 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클(cycle)을 포함하지 

않는다는 조건에 근거하여, 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택.

□ 크러스컬 알고리즘의 순서

 - 먼저, 그래프의 각 간선(edge)들을 가중치의 오름차순으로 정렬.

 - 정렬된 간선들의 리스트에서 싸이클을 형성하지 않는 간선을 찾아 최소비용신장 트리(MST)의 집합에 추가

 - 만약 사이클을 형성하면 그 간선은 버린다.

□ 시간 복잡도

KruskalMST(G)

입력 : 가중치 그래프 G=(V,E), |V|=n, |E|=m

출력 : 최소 신장 트리 T

1. 가중치의 오름차순으로 선분들(E)을 정렬. 정렬된 선분 리스트를 L  ----정렬하는데 O(mlog m)시간(단, m은 입력 그래프에 있는 선분의 수)

2. T=0 //트리T를 초기화하는것이므로 O(1)

3. while(T의 선분 수 < n-1){ //while루프는 최악의 경우 m번(그래프의 모든 선분이 while루프 내에서 처리되는경우)

L에서 가장 작은 가중치를 가진 선분 e를 가져오고, e를 L에서 제거

4. L에서 가장 작은 가중치를 가진 선분 e를 가져오고, e를 L에서 제거

5. if(선분 e가 T에 추가되어 사이클을 만들지 않으면) 

      e를 T에추가

  else e를 버림. //e가 T에 추가되어 사이클이 만들어지는 경우

}  

6.return 트리 T //T는 MST

while루프내에서는 L로부터 가져온 선분 e가 사이클을 만드느니를 검사하는데 이게 O(log m)이 걸림.

따라서, O(mlog m)+O(mlog m) = O(mlog m)