대엉코딩

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인 노드를 가리키도록 구조를 바꿈

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

0. 시작에 앞서...

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

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

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

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

1. 최소신장트리

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

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

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

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

2.프림알고리즘의 아이디어

- 프림알고리즘은 트리를 점점 키워나가는 알고리즘이다.

- 먼저, 임의의 starting vertex를 선택한다.( 보통 그것이 root가 된다.)

- 연결된 간선 중 가중치가 작은 정점들을 차례대로 붙여나간다.

- 정점(vertices)들은 3종류의 disjoint categories로 나누어지는데

  1. Tree vertices

  2. Fringe vertices

  3. Unseen vertices

- 맨 처음에 모든 정점들은 unseen vertices이고 fringe set을 거쳐서 tree set으로 들어가게 된다.

  (단, 처음 선택하는 root vertex만이 fringe set을 거치지 않고  tree set에 들어가게 된다.)

- 예시로 한번 살펴보자(Example)

(1) 그래프는 아래와 같고 A라는 점을 root로 선택해서 시작한다고 가정.

(2) root를 제외한 모든 정점들은 unseen으로 setting

A에서 인접한 정점들을 fringe set에 넣어준다.

(3) (2)에서 가장 가중치가 적은 B를 선택해서 tree set에 넣고 다시 트리 정점으로 부터 인접한

     정점들을 fringe set에 넣는다. B와 인접해있는 C가 추가되었고..

     간선이 중복되는 경우가 있는데 이 경우 선택이 필요하다.

     AG(3) VS BG(6) 인데 AG가 가중치가 더 적으므로 AG를 선택한다.

(4) 이와 같은 과정을 모든 정점을 포함할 때 까지 하는 것이다.

     각 과정에서 가장 가중치가 적은 간선에 연결된 정점을 선택한다는 점에서 그리디 라고도 할 수 있겠다.

     FRINGE SET 은 Min Priority Queue를 이용하면 편하다.

3. Prim's Algorithm

4. 분석 (Analysis)

- 어떤 구조로 fringe set을 구현하느냐에 따라 차이가 있다.

- 일단, 모든 정점이 fringeset을 거쳐 tree set에 하나씩 들어가므로 (정점의 개수를 n이라 하면)

- unsorted array로 구현시 O(n^2)이라고 할 수 있다. 

- 힙으로 구현하면 fringe set에 삽입하는 시간을 O(log n)으로 줄일 수 있다.

- 프림 알고리즘의 경우 정점 개수에 dependent하므로 

- 그래프가 dense(간선이 많을 경우) 할 경우 프림의 알고리즘이 유리하다.