[알고리즘] 3. MST - Kruskal 알고리즘

1. Kruskal 알고리즘의 Idea

• 모든 Edge들을 weight가 작은 순서부터 대입하기 (No Cycle)
• Spanning Tree가 될때까지 이 과정을 반복 (최종적으로 node $n$개 - edge $n-1$개가 되어야 함)

 

 

2. Kruskal 알고리즘의 정당성 증명

- 입력 그래프: $G = (V, E)$
- Edge Set인 $T_{mst}$ 는 정답 중 하나라고 가정
- 알고리즘이 끝난 후 Prim 알고리즘이 가지고 있는 edge set $T$는 $T_{mst}$가 될 것이다.
※ 주의사항: $T_{mst}$는 증명 중간에 바뀔 수 있기 때문에 미리 잡고 시작할 수 없다. 하지만 정답이라는 사실은 항상 유지된다!

$\exists\  T_{mst} \rightarrow T \subseteq T_{mst}$ : Kruskal Algorithm이 가지고 있는 edge set $T$는 어떤 정답의 부분집합임을 증명하자.

• Base: 알고리즘 시작 시 node 1개, edge 0개이므로 $T = \varnothing$ 이다. 따라서, $T \subseteq T_{mst}$ 가 항상 성립한다.
• Step: 어떤 시점에 $T \subseteq T_{mst}$ 라고 가정하자. 이후 한 스텝을 진행해서 Kruskal Algorithm이 edge $e$를 추가하고 현재 edge set 은 $T' = T \cup \left\{ e \right\}$ 이다.
  • Case 1: $T' \subseteq T_{mst}$ 이면 명제 성립하고 끝!
  • Case 2: $T' \nsubseteq T_{mst}$ 이면 반드시 사이클이 생성된다. 이 경우 사이클 내부에 $(e_1 \neq e) \ \land (e_1 \notin T)$ 를 만족하는 edge $e_1$이 반드시 존재한다.

위의 Case 2 에서 $W(e_1)$ 과 $W(e)$ 의 대소관계에 따른 케이스를 나눠서 생각해보자.

• Case 1: $W(e_1) > W(e)$ 이면 $(T_{mst} - \left\{ e \right\}) \cup \left\{ e_1 \right\}$ 인 더 좋은 답이 존재하게 되므로 $T_{mst}$의 정의에 모순된다.
• Case 2: $W(e_1) < W(e)$ 이면 Kruskal Algorithm 에 의해 $e_1$이 먼저 추가되었어야 한다. 따라서 알고리즘에 모순된다.
• Case 3: $W(e_1) = W(e)$ 이면 $(T_{mst} - \left\{ e \right\}) \cup \left\{ e_1 \right\}$ 이것도 정답이 된다. 이 집합을 $T'_{mst}$ 라고 하면 $T' \subseteq T'_{mst}$ 이므로 명제가 성립한다. 증명 끝!!

 

 

3. Kruskal 알고리즘의 구현과 성능

• Edge 저장소: weight에 따라 정렬해서 저장할 배열 생성해서 구현.  (사용 시간: $m \log m$)
• Union Find: 노드가 연결되어 있는지 확인하는 용도. 연결되어 있지 않으면 Edge를 추가하고, 연결되어 있으면 그 Edge는 버린다. (사용 시간: $n$)

$$\therefore T(n) = O(m\log m)$$

 

 

4. Prim, Kruskal can find any solution

Prim Algorithm 과 Kruskal Algorithm 은 항상 모든 솔루션을 찾을 수 있다. 알고리즘의 정답을 여러가지 답들 중 아무거나 $T_{mst}$ 하나로 고정하자. 이제 알고리즘이 이 답을 찾을 수 있음을 보이면 된다. 

알고리즘이 $T$까지 만든 상태에서 $T_{mst}$에 속하지 않는 Edge $e$를 넣었다면, $T \cup \left\{ e \right\}$는 반드시 Cycle이 된다. 이때 Cycle 내에 다른 엣지 $e_1$이 존재하고, 반드시 $w(e_1) = w(e)$ 를 만족한다. 즉 $e_1$도 원래 이번 스텝에서 고려 대상이였고, 이 때 $e_1$을 추가했다면 $T_{mst}$에 속하게 되었을 것이다. 따라서 Prim 알고리즘은 반드시 $T_{mst}$를 찾을 수 있다. 마찬가지로 Kruskal 알고리즘도 모든 Solution을 반드시 찾아낼 수 있다. 

이 사실을 이용하여 "그래프의 모든 엣지들의 weight 가 다를 경우 답은 유일함" 을 증명할 수 있다. Prim, Kruskal 은 $W(e_1) = W(e)$ 인 경우에만 답을 여러개 구할 수 있다. 모든 Edge들의 weight가 다르면 이런 경우가 존재하지 않으므로, $T_{mst}$에 속하지 않는 Edge $e$ 자체가 존재하지 않는다. 따라서 답은 유일하게 $T_{mst}$ 하나로만 정해진다.