Union Find

합집합 찾기

Minimum Spanning Tree

Given a Graph, find Subset of Edges so that a Connected Graph results with Minimum sum of edge costs

Weighted (비용이 있는)그래프

연결된 그래프가 주어지고 edge의 일부를 골라서 그 edge로 갔을 때 connected이고 edge의 최소 비용이면 tree

 

▶ tree connected Acyclic Graph (연결되어 있고 사이클이 없는 그래프) 

만약 사이클이 있다면 한 edge를 버려도 됨 - 연결되어있으며 비용을 줄일 수 있기 때문임 (사이클이면 minimum이 아님)

 

Kruskal Algorithm

• Keep adding Edge
  • From smaller weights 가장 작은 수부터 edge를 추가함
  • As long as no Cycle results 사이클이 생기지 않는 것만 추가함
  • Until N-1 Edges are added 노드의 개수 - 1 만큼 트리를 생성함

N-1개의 edge를 추가하지 못했는데, 더 이상 추가하지 못할 수 있음

 

Q. connected graph 가 주어지면 항상 답이 있는가?

A. 항상 존재한다

Q. connected praph 가 주어지면 kruskal algorithm은 항상 답을 찾는가? (minimum spanning tree를 항상 찾는가)

→ 정확성

Q. 어떤 성능으로 구현할 수 있는가 / 성능 파트의 union find

→ 성능

 

Kruskal Correction idea

• Adding Smallest Edge "that does no make a Cycle"
  사이클을 만들지 않는 가장 작은 엣지를 추가함
• If it makes a Cycle, then you cannot add the Edge
  사이클을 만들면 엣지를 추가할 수 없음
• if you insist on adding the edge, then you have to remove an edge with smaller cost
  어떠한 한 엣지를 추가하고 싶은데, 사이클이 생긴다면 다른 더 작은 엣지를 빼고 새로운 엣지를 추가해야함 - 논리 충돌

* 더 작은 엣지를 빼는 것이 좋은 결과를 이끌어 오는 경우는 제외해야함 ex) 5를 연결하면 다음에 45/ 20을 연결하면 다음에 10

 

 

Implementation Consideration

(node1, node2, weight)로 주어진다고 생각

• weight를 기준으로 sorting → From smaller weights 조건 만족
• sorting한 순서대로 보며, 추가할지 추가하지 않을지 체크 → no Cycle results 

Q. (a,b,w)를 추가했을 때 사이클이 생기느냐 == 같은 connected compont(동치관계)

A. DFS를 사용하여 만약 a,b가 같은 그룹에 있으면 추가하면 안됨 (추가한 엣지들로만 dfs)

 

성능

DFS : O(N)시간이 걸림

전체 크루스칼 알고리즘의 시간 : O(MN)시간 (M:edge 개수)

 

Union/Find or Disjoint Set

크루스칼 알고리즘 / minimum spinning tree 와 역할은 같음

• N items 어떤 시점에 아이템들이 모인 group이 있음
• Initially N groups with 1 item each 맨 처음은 한개 짜리 set으로 이루어짐

이후로 두 가지의 작업을 할 수 있음

1. Union(a, b) : Join 2 groups (the group a belongs to and the group b belongs to) into one
   두개의 그룹을 합침 - 두 개의 그룹을 나누는 등의 작업을 하지 않음 
2. Find(a) : Return the ID the group a belongs to A가 속한 그룹의 아이디를 알려줌 (번호)
   Running Find(a) and Find(b) will answer if a and b belong to the same group a,b가 같은 set에 속하는지 
   ex) minimum spinning tree에서 a,b의 그룹을 보고 w을 넣을 것인지 결정하는 것

The Structure

• Each item is a Node 모든 아이템은 노드
• Initially there are N trees with one Node each 초기에는 모든 노드가 루트인 트리가 존재함
• After some Union operations
  • Each Tree is one group
  • The root of each tree is the ID of the group 
  • No other restrictions 트리 모양에 아무런 제한이 없다
• A Node stores only the pointer to the Parent (Parent 포인터만 존재함 / 내려갈 필요가 없기 때문)

Performance of Union/Find

• Find : 최악의 경우 O(N) / Tree 모양에 제한이 없기 때문에 좋은 모양으로 만들 수 있음 

Find에 가장 좋은 form : root에 바로 연결되는 것 → Union을 할 때 굉장히 느려짐

 

< 효율적인 트리를 만드는 방법 >

* Heuristics means: idea works but the reason is not very clear

원래 휴리스틱으로 사용하다가 후에 증명이 나오게 된 것

 

• 노드에 노드 개수 or tree height를 적어둠 (tree height가 늘어나려면 노드 개수가 2배가 되어야함)
• 더 노드 개수가 작은 tree를 노드 개수가 큰 tree에 합침

▶ log(N)시간이 걸림 (노드 개수 / tree height에 관계 없이) 

 

* path compression : find할 때마다 노드에 붙이거나 하나씩 올리는 등의 방법으로 경로를 줄임

Valiant's Proof

1. Path compression을 하면 Union/find의 각 operation은 O(log N) amortized time (전체적으로 이정도)
2. One operation takes O(log *N) amortized time
   log*N = k means N = 2^2^2 ... k-1 times
   기하급수적으로 증가함
3. one operation takes O(alpha(N)) amortized time
   A(0,n) = n+1 등으로 진행됨