1. Kruskal Algorithm
크루스칼 알고리즘의 기본 아이디어는 가장 작은 weight의 edge부터 하나씩 추가하는것이다.
단 사이클이 생기면 버리고 다음 weight의 edge를 확인한다.
위으 그림으로 예를 들어보겠다.
가장 작은 비용을 가진 edge는 1노드와 6노드를 잇는 10짜리 노드이다.
이것을 선택한다. 그 뒤로도 작은 순서대로 선택한다.
10, 12, 14, 16 이 다음으로 비용이 적은건 18이지만 18을 선택하면 사이클이 생기기에 그 다음인 22를 선택한다.
위와같이 사이클이 생기지 않게 작은 것들만 골라 spanning tree가 만들어지게 하면 된다.
증명 (proof by induction)
증명하기 전에 몇가지 가정을 이해해야한다.
- Tmst는 많은 정답 Edge set 중 하나 이다.
- T는 prim이 만들어가고 있는 Edge set이다. 알고리즘이 끝나면 Tmst가된다.
T⊆Tmst 를 유지한다는 것을 보이자.
Base : 알고리즘 시작 시 node 1개, edge 0개이므로 T=∅ 이다. 따라서, 가 항상 성립한다.
Step : T에 k개의 노드가 들어있을 때, T⊆Tmst라고 성립하자. 그 다음 순서를 진행하면 새로운 edge가 하나 추가될 것이다. 그 edge를 e 라고 하자. 다음 단계의 T를 T′라고 하면
- Case 1: 이면 명제 성립한다.
- Case 2: 이면 반드시 e를 포함하는 사이클이 생성된다. 사이클 안에는 T에 들어있지 않으면서 e가 아닌 edge가 존재한다. 그 중 하나를 e'라고 하겠다.
e'의 weight에 따라 또 3 case로 나뉜다.
- Case 2-1: 이면 알고리즘은 e'를 추가했을 것이다. 알고리즘은 작은 것부터 선택하기 때문이다.
- Case 2-2: 이면 인 더 좋은 답이 존재하게 되므로 T가 성립된다는 것이 모순
- Case 2-3: 이면 또 다른 정답!
2. 성능
- weight에 따라 정렬해서 저장할 배열 생성해서 구현 : 사용 시간:
- Union Find: 노드가 사이클을 만드는지 확인 : 사용 시간: 거의상수 시간
O(mlogm)
4. Prim, Kruskal can find any solution
Prim Algorithm 과 Kruskal Algorithm 은 항상 모든 솔루션을 찾을 수 있다.
증명은 각 알고리즘의 정당성 증명과 유사하다.
알고리즘의 정답을 여러가지 답들 중 하나를 .
알고리즘이 진행되면서 Tmst로 가고 있다는 것을 보이면 된다.
알고리즘이 까지 만든 상태에서 에 속하지 않는 Edge 를 넣었다면,
는 반드시 Cycle이 되고 이때 Cycle 내에 다른 엣지 존재한다.
- 이면 알고리즘은 e'를 추가했을 것이다. 알고리즘은 작은 것부터 선택하기 때문이다.
- 이면 인 더 좋은 답이 존재하게 되므로 T가 성립된다는 것이 모순
- 이면 또 다른 Case의 정답
위와같은 이유로 반드시 를 만족해야한다.
즉 도 원래 고려 대상이였고, 이 때 을 추가했다면 다른 에 속하게 되었을 것이다.
따라서 Prim 알고리즘은 반드시 를 찾을 수 있다.
마찬가지로 Kruskal 알고리즘도 모든 Solution을 반드시 찾아낼 수 있다.
이 사실을 이용하여 "그래프의 모든 엣지들의 weight 가 다를 경우 답은 유일함" 을 증명할 수 있다.
Prim, Kruskal 은 인 경우에만 답을 여러개 구할 수 있다.
모든 Edge들의 weight가 다르면 이런 경우가 존재하지 않으므로, 에 속하지 않는 Edge 자체가 존재하지 않는다.
알고리즘에게는 선택권이 없다.
따라서 답은 유일하게 하나로만 정해진다
'학부 내용 정리 > [ 2-2 ] 알고리즘' 카테고리의 다른 글
| [ 알고리즘 ] Deadline Scheduling (0) | 2022.10.14 |
|---|---|
| [ 알고리즘 ] 최단거리 : Dijkstra Algorithm (0) | 2022.10.12 |
| [ 알고리즘 ] MST(1) : Prim Algorithm (0) | 2022.10.11 |
| [ 알고리즘 ] 자료구조 내용 복습 (0) | 2022.10.09 |
| [ 알고리즘 ] 정렬(3) : Quick Sort (0) | 2022.10.09 |