4. Minimum spanning tree(MST)

Mininum spanning tree란 weight를 가진 undirected graph가 주어졌을 때, 모든 vertex를 연결하면서 비용을 최소로하는 tree형태(cycle x)의 subgraph이다. 클러스터 분석등 여러 가지 응용에서 쓰인다.

 

1. Greedy algorithm

 

Greedy algorithm은 매 순간 최적인 선택을 하며 그러한 방식으로 진행할 때, 최종적으로 해답에 도달하게 되는 알고리즘이다. 모든 문제에 대해서 적용되는 것은 아니지만, MST를 구할 때 이것을 적용할 수 있다.

- 가정 : connected graph, distinct weights

- Cut : 그래프가 주어졌을 때, 두개의 집합으로 vertex들을 분할하는 것

- crossing edge : 한 집합의 vertex를 다른 집합의 vertex와 연결하는 edge

 

그래프의 cut이 주어졌을 때, 두 집합을 연결하는 crossing edge중 비용이 최소인 것만 MST에 포함된다

만약, 비용이 최소가 아닌 crossing edge만 포함된다면 최소 비용이 아니게 되고, 비용이 최소인 edge를 포함한 상태에서 다른 edge를 MST에 포함할 경우 cycle이 형성되므로 불가능하다.

 

선택되지않은 edge를 gray, crossing edge를 black으로 했을 때, 규칙은 다음과 같다.

1) 모든 edge가 gray인 상태로 시작한다.

2) black edge가 없는 cut을 찾고, 최소 비용 crossing edge를 black으로 칠한다.

3) black edge가 V-1개가 될 때까지 반복한다.

 

distinct weight가 아닌 경우에도, 동일한 weight중 하나를 선택하여 MST를 구할 수 있다.

connected graph가 아닌 경우에도 각각의 부분 그래프에 대해 MST를 구할 수 있다(Minimum spanning forest)

 

2. Edge-weighted graph API

 

Edge의 API는 다음과 같다.

 

Edge(int v, int w, double weight)

int either()    //return one vertex

int other(int v)    //return other vertex

int compareTo(Edge that)   //compare weight between edges

double weight()

 

Edge-weighted graph의 API는 다음과 같다.

 

EdgeWeightedGraph(int V)    //create an empty graph with V vertices

void addEdge(Edge e)    //add edge

Iterable<Edge> adj(int v)   //edges incident to v

 

MST의 API는 다음과 같다.

 

MST(EdgeWeightedGraph G)

Iterable<Edge> edges()

 

3. Kruskal's algorithm

 

MST를 만드는 규칙은 다음과 같다.

1) 모든 Edge를 오름차순으로 정렬시킨다.

2) 비용 가장 작은 Edge를 하나씩 꺼내고, cycle이 생기지 않는다면 MST에 추가함을 반복한다.

 

Kruskal's algorithm은 greedy algorithm의 special case이다. 

예를 들어, Kruskal's algorithm에 따라 cycle을 형성하지않는 Edge E = v - w 인 Edge를 추가시킬때, v와 연결된 tree의 vertex들을 하나의 집합으로 보고, w를 포함하는 나머지 모든 vertex들을 또 다른 하나의 집합으로 본다면(CUT찾기), 두 집합간에 crossing edge는 없는 상태이고 v - w보다 더 작게 연결하는 비용의 Edge는 존재하지 않으므로, E는 MST에 포함된다.

 

구현의 경우 정렬과 최소비용 Edge를 꺼내는 것은 Prioity Queue를 이용하면 되므로, 실행시간은 build pq, delete-min를 따졌을 때, ElogE 정도의 실행시간이 소요된다. 또 한가지는 Cycle이 생기는지 여부를 판별하는 것인데, 이것은 앞서 배운 union-find 과정을 추가하기만 하면 된다. e = v - w 에서 v, w가 같은 집합내에 있다면 추가시 cycle이 생성되는것으로 판별한다.

 

2. Union-Find

 

union-find는 cycle생성여부를 weighted QU + path compression알고리즘에서 log*N 성능으로 찾을 수 있다. (우주에서 일반적으로 이것은 6이하의 숫자)

union은 V번, 연결여부 확인은 E번 이루어 지므로 각각 수행시간은 Vlog*V, Elog*V 이다.

최종적으로, 전체적인 실행시간은 ElogE가 된다.

 

4. Prim's algorithm

 

MST를 만드는 규칙은 다음과 같다.

1) 특정 vertex를 하나의 tree인 T로 설정한다(T = MST)

2) T의 vertex들과 연결된 edge 중 최소비용edge를 T와 연결시켜 tree를 성장시킨다.

3) V-1개의 Edge가 T에 추가될 때까지 반복하고 최종적으로 T가 MST가 된다.

 

Prim's algorithm 은 greedy algorithm의 special case이다. 

tree T의 vertices가 하나의 집합, 나머지가 다른 하나의 집합이 된다. 집합간에 crossing edge가 없으므로 이것을 cut으로 볼 수 있다. 

 

구현의 경우, T와 연결된 edge중 최소비용edge를 어떻게 선택할 것인지에 따라 여러 방법이 가능하다.

크게 Lazy solution과 Eager solution이 있다.

- Lazy solution

 

Lazy solution에서는 현재 T의 vertex들와 연결된 모든 edge들을 담고있는 Prioity Queue와, 특정 vertex가 T에 포함되었는지 여부를 담고있는 marked[] 배열을 유지시킨다.

규칙은 다음과 같다.

1) PQ에서 delete-min을 했을 때 e = v - w 에서 v, w가 모두 marked가 되어있다면 다시 delete-min을 하고, 그렇지 않고 w가 unmarked라면 해당 Edge를 MST에 포함시키고, marked시킨다.

2) w가 MST에 포함되었으으므로, w와 연결된 모든 edge들을 PQ로 집어넣는다(Lazy)

3) 1번으로 돌아가 V-1개가 MST에 포함될때까지 반복한다.

 

실행시간은 PQ에서 꺼내고 삽입하는데 logE시간, 횟수는 E번이므로, ElogE에 비례한다.

 

- Eager solution

 

Lazy solution의 한가지 문제는 MST에 추가된 vertex와 연결된 모든 edge를 넣기 때문에, tree가 성장할 수록 너무 많은 Edge들이 추가되어 매우 큰 저장공간을 필요로 하게 된다는 점이다.

출처 : coursera, Algorithm part2 lecture

 

예를 들어, 위와 같이 그래프가 주어졌다고 생각해보자. 먼저, MST에 0을 넣고, 0과 인접한 모든 Edge를 PQ에 넣는다.

Delete-min을 수행하였을 때, 7이 unmarked이므로 7을 MST에 추가하고, 7과 인접한 모든 Edge를 PQ에 넣는다.

현재 0 - 4 가 이미 추가되어있고, 7 - 4 를 추가해야되는 상황이다. 만약 7 - 4가 더 비용이 작다면, 추후에 4가 MST에 연결될 때 것은 0 - 4 로 연결될 수 없으므로 0 - 4는 PQ에서 삭제하는것이 낫다. 

우리는 이러한 연산을 위해서 최대 V개의 Edge를 가지는 Prioity Queue를 생성하고, PQ내 Edge위치를 Indexing시켜 바로바로 찾을 수 있도록 한다. 이 때, index는 각각의 vertex를 의미하므로 크기는 V이다.

예를 들자면, 처음에는 0-7, 0-2, 0-4, 0-6이 PQ에 추가된다.

이것은 각각 7, 2, 4, 6으로 indexing된다.

delete-min시 0-7이 나온다고 가정하고, MST에 7이 없으므로 7-4, 7-5, 7-1, 7-2가 추가되어야한다.

그런데 이것의 index는 각각 4, 5, 1, 2인데, 2, 4가 이미 PQ에 있다. 일단 없는 1, 5는 추가된다.

0-4보다 7-4가 weight가 더 작고, 0-2보다 7-2가 weight가 더 크다고 해보자.

우리는 index 4인 PQ의 Edge를 찾아서 7-4의 Edge로 변경하고, 해당 node의 weight값이 변경되었으므로, swim함수를 통해 PQ의 우선순위 규칙을 회복시킨다. 7-2는 weight가 더 크므로 버린다.

이런식으로 PQ를 유지시키고, MST를 구한다면 PQ의 최대크기가 Index의 크기인 V가 되어 저장공간을 효율적으로 사용할 수 있으며, 실행시간은 Edge의 갯수만큼 PQ에서 변경/추가/삭제 연산을 수행하므로 ElogV가 된다.

 

5. Context & Application

 

MST를 찾는 최적의 알고리즘은 무엇일까? 

1984년도에도 Fredman-Tarjan에 의해 Elog*V 수준의 알고리즘이 발견되었는데 log*V가 우주에서 6이하임을 가정하면, 거의 상수에 근접하므로 linear time에 매우 가깝다고 볼 수 있다. 이후에도 꾸준히 알고리즘이 발견되어, 거의 선형에 점점 가까워지고있지만, 아직 완전한 선형의 알고리즘은 아직 open-problem이라고 한다...

 

MST는 여러 응용에도 사용될 수 있는데, 모든 도시를 연결하는 최적의 경로 그래프를 찾는 것에서도 활용될 수 있다.

또다른 응용에서는 clustering 이 있는데, k개의 cluster가 나올 때까지 kruskal's algorithm을 실행하거나, Prim's algorithm을 실행한 뒤, k-1개의 max weight edge를 제거하는 방식으로 clustering을 할 수 있다.