MST, Kruskal, Union-find, Prim

edge의 합을 최소로 하면서 모든 node를 커버하는 tree 만들기

Kruskal’s Algorithm (Greedy Approach)

cycle을 만들지 않으면서 가장 작은 weight의 간선을 차례로 추가

Proof Kruskal is optimal

즉 가장 작은 간선을 추가해도 MST가 유지된다는 것이다.

pf) 귀류) 가장 작은 간선 e가 MST에 포함되지 않는다고 가정하자. 그렇다면 다른 e’로 연결되어 있을 것이다. (T)

그 상태에서 e’를 없애고 e를 추가하면 (T’) cost(T’) ≤ cost(T)일 것이다. 즉 MST이다. 따라서 e를 포함한 MST가 있으니 모순!

Union-Find: Checking Exsitence of Cycle

사이클을 만드는지 어떻게 확인할까?

• makeset(x): x 하나 가진 집합 생성
• find(x): x가 속한 집합 찾기
• union(x,y) 두 set 합치기

즉 간선의 두 node에 대해 find를 했을 때 같은 곳에 있으면 기각시키고 다른 곳에 있으면 이어준 뒤 두 set을 합치는 식이다.

Union-find: Tree Implementation

조금 더 빠르게 할 수는 없을까? → tree 사용

find(x)는 x가 있는 tree의 root 반환 union은 하나의 root를 다른 root 아래에 추가한다. 이때 더 큰 tree의 아래에 작은 tree를 넣는다.