Greedy - Kruskal Algorithm : MST
Kruskal Algorithm - Part 1.
Kruskal_MST(input G) : edge-based approach
-----------------------------------
Sort Edge set 'E' : my ranking/scoring function.
while NOT solved yet{
select next edge 'e' : from sorted list 'E'
if (cycle check) remove/pass
else add 'e'
if (stop condition) stop
}
==> Edge들을 정렬해서 자료구조에 넣어놓음 (weight가 같은 edge는 random으로 선택해도 무방)
==> 이런식으로 vertex에 정렬된 edge들을 순서대로 추가해나감
==> 순서대로 추가하다가 cycle이 생기면 remove 후, 다음 edge 추가.
Question: how to check 'Cycle' in Kruskal? ==> 가장 핵심적인 아이디어
- set of tree: Forest data structure
- two key operations in Forest: find and union.
- find : root finding in a tree
- union : connect two roots
==> find each roots of i and j.
==> see/check if the two roots are the same.
=> If YES, cycle O.
=> If NO, cycle X. add 'e' => repeat.
Kruskal Algorithm - Part 2.
Kruskal_MST(input G) : edge-based approach
-----------------------------------
1. F <= empty // MST를 담을 자료구조
2. Create 'n' disjoint sets: {v1}, {v2}, .... {vn} // init => vertex들을 각각 하나의 tree(Forest)로 구성
3. Sort Edge set 'E' // edge 정렬 후 E 자료구조에 담음
4. while NOT solved yet { // loop는 edge 개수만큼 돌아감(E에서 edge를 뽑아서 F에 추가/할지 말지 결정하니까)
select next edge 'e' : from sorted list E // E에서 다음 edge 'e'를 뽑음
If (cycle check) : 'e' connects two subsets, then, merge them and add e to F.
// e가 cycle을 만들지 않는다면, e를 F에 추가함.
If stop condition TEST. // F.length (연결된 edge의 개수)가 V-1(모든 정점의 개수 -1)이면 종료
}
CYCLE CHECK : find-union operaions
-------------------
e = next edge: {i, j}
p = find(i)
q = find(j)
If p != q ==> connect/merge,
add e to F.
Analysis:
T(n) = ?, |V| = n, |E| = m
1. init: theta(n) // n개의 vertex를 하나의 tree(forest)로 초기화
2. sort: depending on the specific algo. => O(mlogm) // edge 개수 m을 sort
3. while loop : O(m*cycle-check) // edge의 개수만큼 loop * cycle check하는 시간
* find => balanced tree : logn ( 원래 이진탐색은 logn이야 )
=> skewed tree : n ( 편향되어 있기 때문에 worst 경우 n개의 node를 다 타고 올라갈 수도 있음)
====> Data structure에 따라 다름
* union => 상수시간 (걍 F 뒤에 추가만 하면 됨)
: : O(m*cycle-check) = O(m * alpha(n,m)) ==> find operation을 O(logn)보다 작게 만듦
**** alpha time ==> find, union operation을 ... 암튼 뭐 많이 연구했대
=> 아무튼 alpha time이 O(logn)으로 접근한다면 O(mlogn)이 됨.
4. remaining ops.
==> Kruskal algo. T(n,m) = O(mlogm) :: 결과적으로 이게 된다.
==> 왜? #edges: n-1 <= m <= n(n-1)/2 :: 일반적으로 edge의 개수는 최소 vertex 개수-1 ~
=> O(mlogm) > O(mlogn) (일반적으로 edge의 개수가 vertex의 개수보다 많다)
** stop condition을 |E| = |V-1|로 주면 edge의 개수가 vertex의 개수보다 적어지는데 이건 뭐지..?
라는 멍청한 생각을 잠깐 했는데, 애초에 여기서의 n과 m은 초기 vertex와 edge의 개수임. 나중에 구한 MST의 V, E가 아니라. ==> 당연히 MST를 구하는 문제인데, 애초에 MST인 tree를 제시하겠니?
어찌됐든, edge를 sort하는 시간과, loop를 돌며 cycle check하는 시간 둘 중 비교를 했을 때, edge sort를 구하는 time이 더 upper bound 라는 것.
Proof: similar Prim's algo ==> 알아서 해보기
Kruskal's Theorem: "Kruskal's algo produces MST"
(Base) F = empty is promising.
(H) Assume : F is promising (MST T= (F))
(Induction) F + next edge is MST
** 사실 여기서 좀 헷갈리는게, Prim이야 vertex 기준으로 하나씩 edge를 추가해가는거니까, edge를 추가하면 그게 또 하나의 MST가 되는게 맞는데, kruskal은 그냥 edge 정렬 순으로 vertex를 연결하는거라, edge를 F에 추가한다고 그게 하나의 MST가 되지는 않음. set of MST가 맞지 않나 싶기도 하고(최종 결론적으로는 하나의 MST를 만들지만 중간과정에서는?), set of MST이려면, 추가하는 edge가 cycle을 만들지 않아야 해서 induction을 cycle을 안만든다. 이걸 해야되나 싶기도 한데, 이미 kruskal 알고리즘 내에 cycle을 거르는 과정이 있는데....
그냥 contradiction을 두개 세우기로 함.
Proof on Induction is required => Lemma.
==> proof by contradiction
Contradiction 1): NOT F + next edge is set of MST
Contradiction 2): set of MST는 하나의 MST가 되지 못한다.
T(F)
1) next MST : kruskal's algo. T(kru) = (F+e) => set of MST x
=> 이게 옳으려면, T(kru)는 edge를 추가 했을 때, cycle을 만들어야함
But, kruskal은 애초에 cycle을 포함하지 않는 edge를 선택하기 때문에 cycle을 만든다는 말을 conflict.
2) T(kru) = (F+e) , e is last element of Edge list ==> MST x
=> 이게 옳으려면, edge list의 마지막 edge까지 추가했을 때, 하나의 MST가 되지 못해야 함.
But, 이미 주어진 graph가 connected graph 이므로, 마지막 edge까지 추가한다면, set of MST는 주어진 connected graph의 edge에 의해 하나의 MST가 될 수밖에 없다, 따라서 하나의 MST가 되지 못한다는 말은 conflict가 생긴다.
*connected graph => 모든 두 node 사이에 edge가 존재하는 graph
즉, contradiction의 conflict가 발견되었으므로 Induction을 proof 할 수 있게 된다.
Prim's algo vs Kruskal's algo.
: proof done.
: time complexity? O(n^2) vs O(mlogm)
===> more research is required.
===> advance O(n^2)
* MIT Lecture note 6.046J Spring 2015 Greedy & MST
cut and paste
prim - Extract-Min => priority queue => greedy
=> O(v^2) => O(ElogV) => O(E+VlogV)
kruskal ====> O(E)
==> CS가 경쟁하면서 계속 발전하고 있다......아...............