Kruackal's Algorithm(크루스칼 알고리즘)

0. 시작에 앞서...

- Minimum-Spanning-Tree 문제는 그래프의 최적화 문제 중 유명한 하나의 문제이다.

- 모든 정점을 최소비용으로 연결할 수 있는 트리를 구하거나 그 비용을 알아내는 문제.

- 즉 최적해(optimal solution)을 찾아내는 문제.

- 최소신장트리를 구하는 유명한 알고리즘으로 Prim과 Kruscal이 있는데 이번 시간에는 Kruscal 알고리즘을 다룬다.

 

 

1. 최소신장트리

- 최소 신장 트리( MST )란, 주어진 그래프에서 최소한의 비용으로 트리를 만드는 것

- 최소신장트리는 무향연결그래프에서 정의되며, 즉 connected, undirected,weight graph.

- 그래프의 weight는 그래프를 이루고 있는 subgraph들의 간선 가중치의 합.

- 트리 이므로 당연히 사이클이 발생해서는 안된다.

 

 

2. Union-Find data structure

- 서로 교집합이 없는 집합들을 모아놓은 자료형 ( disjoint set )

- operation : find(u) -> set id를 통해서 집합을 구분하는데 u라는 노드를 포함하고 있는 집합의 set id 를 return 한다.

                 union(u,v) -> u,v 두 노드가 각각 포함된 두 집합을 합집합한다.

 

3.Kruskal's Algorithm

- 접근 방식이 prim과 약간다르다고 할 수 있다.

- greedy technique을 이용한 알고리즘

- 각 노드들을 tree로 만들어 forest를 구성하고 그 tree들을 합쳐나간다.(merge)

- 간선에 dependent하다.

- 1. 가장 가중치가 적은 간선을 선택.

  2. 간선에 인접한 두 노드에 대해서 각각 find 연산을 수행한다.

  3. find(u) 와 find(v)의 리턴값이 다르면 두 노드가 서로다른 set에 포함되어있었던 것 이므로

     간선의 가중치를 추가해주고 두 노드에 대해 union(u,v)연산을 수행한다.(합집합)

  4. 만약 리턴값이 같다면 이미 두 노드는 같은 집합에 포함되어 있으므로 다른 작업을 수행하지 않는다.

  5. 모든 노드들이 포함되어 하나의 tree가 되면 위의 작업들을 반복하던 것을 종료한다.

 

4. Example

(1)

(2)

(3)

(!! 집합의 SET ID는 집합의 노드 중 알파벳 순으로 가장 작은것이 SET id 라고 가정)

 

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12) 모든 노드가 TREE에 포함되었다.(MST)

5. 분석(Analysis)

- 시간복잡도 O(mlogm)  // m:간선의 수

- 크루스칼은 간선에 dependent하므로 그래프가 희소(sparse)

- 즉, 간선이 별로 존재하지 않는 그래프에서는 프림보다는 크루스칼이 유리하다.

- 시간복잡도, 즉 성능의 경우는 union-find 자료구조(data structure)을 어떻게 구현하느냐에 따라

   매우 상이하다.

- union find ADT를 구현할 때 

   weighted union : 더 큰 집합 뒤쪽에 작은 집합을 붙임

   path-compression: find연산을 한번 수행할 시 뒤쪽에 달린 노드들이 모두 setid인 노드를 가리키도록 구조를 바꿈

 이러한 방법들을 사용한다면 약간의 성능 향상을 기대할 수 있다.