Union Find & an Application

Minimum Spanning Tree

• cycle이 없지만, 전체를 커버한다.
• 루트x, 방향성x

노란 부분이 minimum spanning tree

Kruskal Algorithm

• 가장 작은 weight부터 edge를 추가한다.
• cycle은 없게 한다.
• N-1까지의 edge를 추가한다. > tree조건도 만족 

Why is Kruskal Correct?

• cycle을 만들지 않는, 가장 작은 edge를 추가한다.
  ↔ 만약 추가하려는 edge가 cycle을 만든다면, 추가하지 않는다.
• 해당 edge를 추가하려면 cycle을 구성하고 있는 edge중 하나를 빼야한다.
  > 작은 edge부터 추가하고 있으므로 cycle 중 하나는 빼면 추가 하려는 것보다 더 작은 edge가 빠짐
• 최단거리 아님. 모순 발생
  > 완벽한 증명은 아니지만 이런 아이디어로 진행된다. 

Union/Find or Disjoint Set

• N개의 items(nodes)
• 처음엔 하나의 item이 하나의 group이다. > N groups with 1 item each
• 두개의 operations
  • Union(a, b): 2개의 그룹을 하나로 join
  • Find(a): 해당 그룹이 가지고 있는 ID를 리턴

The Structure

• 각각의 item은 하나의 node
• 처음엔 하나의 node가 하나의 tree
• 몇 번의 union operations 후에
  • 각각의 tree가 하나의 그룹
  • 각 tree의 루트가 ID
  • 트리 모양에 제한 없음
• node는 오직 parent의 포인터만 가지고 있음. child는 어디있는지도 모름!
  > find는 root를 찾는 것 > 올라가기만 하면 됨 > child 굳이 알 필요 없음 

example

위와 같은 상황에서 Find(2) = 4

worst case에서 Find는 O(N)이 걸린다.

best form

Find가 매우 빨라지는 형태이지만,

다른 트리와 Union연산을 할 때 child를 찾을 수 없으므로 저런 모양은 길게 유지 불가함. 

> 모양 유지를 위해선 child를 계속 루트에 붙여야되는데 child 찾는거 자체가 불가 

 

Heuristics

: Idea works but the reason is not very clear

• Union 연산 시 node 수 큰 쪽에 작은 트리를 붙임
• 두 트리간의 node 개수 차↑ > 어차피 큰 쪽에 붙음 > height 안 늘어남
• height가 똑같은 2개의 트리가 Union될 때만 height가 늘어난다. 
  > 비슷한 논리로 tree height가 logN 임을 알 수 있다.