on
[알고리즘] 4. MST - Kruskal 알고리즘
[알고리즘] 4. 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'
subseteq T_{mst}$ 이면 반드시 사이클이 생성된다. 이 경우 사이클 내부에 $(e_1
eq e) \ \land (e_1
otin 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 은 항상 모든 솔루션을 찾을 수 있다.
$W(e_1) = W(e)$ 이면 $(T_{mst} - \left\{ e \right\}) \cup \left\{ e_1 \right\}$ 이것도 정답이 된다. 이 집합을 $T'_{mst}$ 라고 하면 $T' \subseteq T'_{mst}$ 이므로 명제가 성립한다. 증명 끝!!
두 알고리즘의 정확성 증명에서 Case 3를 보면 $T_{mst}$ 를 찾기 위해 Edge $e$를 넣었지만, $e_1$ 을 넣어도 $T`_{mst}$ 라는 새로운 정답을 만들 수 있었다. 이를 통해 Prim 과 Kruskal 알고리즘은 모든 Solution을 반드시 찾아낼 수 있음을 알 수 있다.
이 사실을 이용하여 "그래프의 모든 엣지들의 weight 가 다를 경우 답은 유일함" 을 증명할 수 있다. Prim, Kruskal 은 $W(e_1) = W(e)$ 인 경우에만 답을 여러개 구할 수 있다. 모든 Edge들의 weight가 다르면 이런경우가 존재하지 않으므로, 답은 유일하게 정해진다.
from http://kucse20yjwon.tistory.com/69 by ccl(A) rewrite - 2021-11-14 16:26:43