[알고리즘2] Union Find

복습하기 위해 학부 수업 내용을 필기한 내용입니다.
이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다.
그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다.

▶Contents

• Union Find
• Quick Find
• Quick Union

 

▶Union Find

• N개 객체가 주어진다.
  • 0 ~ (N-1)까지 정점(vertex)으로 표현된다.
  • 간선(edge)이 없는 상태에서 시작한다.
• 2개의 명령 수행이 필요하다.
  • Union(a, b) : 점 a와 b를 간선으로 연결
  • Connected(a, b) : a와 b를 연결하는 경로 존재하는지 True/False로 응답한다. (Find라고도 한다.)
• 값이 Union 됨에 따라서 Connected(Find) 값이 달라진다.
• 한마디로 연결 상태가 동적으로 계속 변한다. (그때그때 다시 답을 확인할 필요가 있다.)

 

• union(a, b), connected(a, b)를 수행하려면 그래프 연결 상태를 저장할 필요가 있다.
  • Adjacency list 방식 : adj[v]에 v에 인접한 정점 목록을 저장
    • union(a, b) : O(1) 상수 시간에 해결 가능하다.
    • connected(a, b) : 그래프가 커지면 비효율적이다. O(E 간선의 개수)
    • 경로를 찾거나, 간선을 삭제할 경우에는 개별 간선 정보가 꼭 필요하다.
  • connected component에 속하는지 계속 기록하고 업데이트한다.
    • connected component : 서로 연결된 정점들의 maximal한 집합
    • ids[]를 사용해 각 객체가 어느 connected component에 속하는지 기록한다
    • ids[i] : 객체 i가 속한 component의 id
    • id : 서로 다른 component에 서로 다른 숫자 부여한다. 속한 객체 중 가장 작은 번호를 사용한다.

728x90

▶Quick Find

• ids[]를 사용해 각 객체가 어느 connected component에 속하는지 기록한다.
• ids[i] : 객체 i가 속한 component의 id
• id : 서로 다른 component에 서로 다른 숫자 부여한다. 속한 객체 중 가장 작은 번호를 사용한다.

• Q. 왜 이렇게 저장하는 가?
  • A1. Connected(a, b)를 빠르게 할 수 있음. 그래서 Quick Find라고 부른다.
  • A2. N x N 배열이나 adj_list를 사용해 개별 간선 정보를 일일이 저장하지 않아도 된다.
    • 1 x N 배열에 필요한 정보를 다 담을 수 있다.

ids[i] = i로 초기화

def connected(a,b):
	return (ids[a] == ids[b])

def union(a,b): 
	ids[i] == ids[b]인 모든 i에 대해 ids[i] = ids[a]로 값 교체
	#혹은
	ids[i] == ids[a]인 모든 i에 대해 ids[i] = ids[b]로 값 교체

위에 간단한 슈도코드를 아래의 코드로 바꿔서 작성하였습니다.

N = 8
ids = []
for idx in range(N): 
	ids.append(idx) # 정점 번호로 ids[] 초기화
    

def connected(p, q):
	return ids[p] == ids[q]
    
    
def minMax(a, b):
	if a<b: return a,b
	else: return b,a


def union(p, q):
	id1, id2 = minMax(ids[p], ids[q])
	for idx, _ in enumerate(ids):
		if ids[idx] == id2: ids[idx] = id1

Algorithm	ids[] 초기화	union	find(connected)
Quick-Find	O(N)	O(N)	O(1) - 상수시간

▶Quick Find에서 사용하던 구조의 다른 해석

• connected component를 tree로 본다.
• ids[i] : 객체 i의 parent
• 만약 객체 i가 root라면 ids[i] = i
• connected(p, q) == True if root(p) == root(q)
• union(p, q) : p가 속한 tree 상의 모든 node를 q가 속한 tree 아래로 옮겨 붙이기.

 

▶Quick Union

• connected(p, q) == True if root(p) == root(q)
• root(i) = ids[ids[ids[… ids[i] …]]
  • root를 찾으려면 계속해서 타고 올라가야 한다.
• union(p, q) : root(p)를 root(q) 아래로 옮겨 붙이기.

N = 10
ids = []
for idx in range(N): # ids 초기화
	ids.append(idx)


def root(i):
	while i != ids[i]: i = ids[i]
	return i


def connected(p, q):
	return root(p) == root(q)


def union(p, q): 
	id1, id2 = root(p), root(q)
	ids[id1] = id2

union 할 때마다 root를 찾아야 한다. (O(d) -> 트리의 길이)

Algorithm	ids[] 초기화	union	find(connected)
Quick-Find	O(N)	O(N)	O(1)
Quick-Union	O(N)	O(N)	O(N)

트리가 커지면 깊이가 깊어져서 Quick-Union 할 때 find, union 하는 시간이 오래 걸린다.

 

▶Weighted Quick Union - QU에서 트리 깊이 제한

• union(p, q) : 작은 트리의 root를 큰 트리의 root 아래에 연결한다.
• union후에 depth는 증가하지 않는다.
• 만약 두 tree의 크기가 같다면 그때는 depth가 1 증가한다.

N = 10
ids = []
size = [] # size[i]: size of tree rooted at i
for idx in range(N): 
	ids.append(idx)
	size.append(1)


def root(i):
	while i != ids[i]: i = ids[i]
	return i


def connected(p, q):
	return root(p) == root(q)


def union(p, q): 
	id1, id2 = root(p), root(q)
	if id1 == id2: return #이미 연결
	if size[id1] <= size[id2]: #p가 속한 트리의 사이즈가 작은 경우
		ids[id1] = id2
		size[id2] += size[id1]
	else: #q가 속한 트리의 사이즈가 작은 경우
		ids[id2] = id1
		size[id1] += size[id2]

• 어떤 객체 x의 깊이도 ≤ log2 (N)으로 제한된다.
  • 증명
  • N개 객체 중 임의의 정점을 x라 하자.
  • x의 깊이가 +1 될 때는 x가 속한 트리가 (작아서) 더 큰 트리에 연결될 때
  • 이때 x가 속한 tree의 크기는 최소 2배가 된다.
  • 그런데 이렇게 크기가 2배가 되는 것은 많아봐야 log2 (N) 회
  • x의 깊이가 k번 +1 된다고 가정하면,
  • x가 속한 트리의 크기는 최소 2^k
  • 전체 그래프에 N개의 객체만 있으므로 2^k ≤N
  • 따라서 k ≤ log2 (N)

Algorithm	ids[] 초기화	union	find(connected)
Quick-Find	O(N)	O(N)	O(1)
Quick-Union	O(N)	O(N)	O(N)
Weight QU	O(N)	O(log(N))	O(log(N))