MST _ Kruskal's algorithm

• Greedy algorithm

- 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 답을 도출한다.

- greedy algorithm은 그 순간에 최적이지만, 전체적으로 최적이라는 보장이 없지만, Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어있다.

 

 

• Kruskal Algorithm 동작

- 그래프의 edge들을 weight이 작은 것부터 순서대로 정렬한다.

- 정렬된 edge 리스트에서 순서대로 사이클을 형성하지 않는 edge을 선택한다.

          가장 낮은 weight를 먼저 선택한다.

          사이클을 형성하는 edge를 제외한다.

- 해당 edge를 현재의 MST의 집합에 추가한다.

 

pseudo-code

 

• Example of Kruskal

 

 

- 또 다른 그림 예제

 

 

 

다음 edge를 이미 선택된 edge들의 집합에 추가할 때 사이클을 생성하는지를 체크한다.

        새로운 edge가 이미 다른 경로에 의해 연결되어 있는 vertice들을 연결할 때 사이클이 형성된다.

        추가할 새로운 edge의 양 끝 vertice가 같은 집합에 속해 있으면 사이클이 형성된다.

 

 

• Kruskal 알고리즘의 시간 복잡도

edge가 n개 있을 때, edge를 퀵 정렬과 같은 효율적인 알고리즘으로 정렬한다면 시간복잡도는 O(nlgn)이다.

그래프 내에 적은 숫자의 edge만을 가지는 Sparse Graph(희소 그래프)의 경우 kruskal 알고리즘이 적합하다.