공부/알고리즘2011. 7. 11. 23:10


Disjoint set
A,B 두 집합의 교집합이 공집합일 때, A와 B는 disjoint이다.

Collection
disjoint set들의 집합
collection의 각 set들은 representative member(대표 원소)를 가지고 있다.

Disjoint-set operations
make-set(x) - x를 set으로 만들고 disjoint sets에 추가.
union(x,y) - x를 포함하는 집합과 y를 포함하는 집합을 합침.
find-set(x) - x를 포함하는 집합의 representative member 찾기

union operation의 수는 최대가 make-set operation의 수 -1이다.

Disjoint-set의 활용
Computing connected components
연결된 컴포넌트 계산하기
 
출처 : en.wikipedia.org

그래프가 정적일 때는 Depth-first search로 해결.
하지만 동적일 때는 DFS가 비효율적이다. 새로 들어오면 다시 DFS해야 되니까.
disjoint-sets을 만들고 유지하는 것이 더 효율적. 
Vertex마다 set을 만들고 모든 edge를 체크해서 두 vertex가 같은 set에 없으면 union한다.

disjoint-set data structures 구현 방법
1. Linked-list representation
각각의 set들을 linked list로 표현 할 수 있다.
set 안의 멤버들은 list의 element가 된다.
첫번째 element가 representative이다.
모든 element가 representative를 가리키고 있다.

make-set(x)
Θ(1)
head와 tail 포인터를 자기자신을 가리키게 하고, representative를 가리키는 포인터도 자기자신을 가리킨다.

Find-set(x)
Θ(1)
x의 representative 포인터를 참조하면 한번에 찾을 수 있다.


Union(x,y)
두 linked-list를 붙인다.
앞의 리스트의 tail이 뒤에 붙는 리스트의 마지막을 가리키게 한다.
뒤에 붙는 리스트의 elements들의 representative 포인터를 앞 리스트의 representative를 가리키게 한다.
Θ(m2) 시간이 걸린다. 뒤에 붙는 리스트의 모든 elements들의 representative 포인터를 바꿔줘야 하기 때문.

전체시간
단순하게 구현한 union을 사용하면
O(n^2) (make-set n번, union 최대 n-1번)
union할 때 짧은 리스트를 뒤에 붙이면 시간을 줄일 수 있다.
O(m + n lg n) (m은 총 operation 갯수. n은 총 노드 갯수)

2. Forest representation
각각의 set을 트리로 나타냄.
각각의 member는 자신의 부모를 가리킴
트리의 루트는 representative임.

make-set(x)
부모포인터를 자신을 가리키게 함.

find-set(x)
부모포인터가 자신이면 루트이므로 바로 x를 리턴.
아니면 루트에 도착할 때까지 부모를 따라 올라간다.

running time 개선 방법
1. Union by rank
트리의 높이정보인 rank를 이용해서 높이가 짧은 트리를 긴 트리에다가 붙인다.
union 시간 단축

2. Path compression
find-set할 때 모든 노드가 루트를 가리키게 한다. 한번에 representative를 찾도록.
find-set 시간 단축
 
O(m α(n)), α는 보통 4이하인 상수. 

참고사이트
http://aronze.egloos.com/214354
http://pixelenvy.ca/wa/uf_details.html 

'공부 > 알고리즘' 카테고리의 다른 글

Minimum spanning tree (최소신장트리)  (0) 2011.07.13
Elementary Graph Algorithms  (0) 2011.07.13
Greedy Algorithms  (0) 2011.07.11
Dynamic Programming  (0) 2011.07.09
11장 Hash Table  (0) 2011.07.08


Posted by skyjumps