그래프 알고리즘 - (4) Union-find(disjoint set)
이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다.
1. Disjoint Set과 Union-Find
Disjoint Set
disjoint set은 서로 중복되지 않은 부분 집합들로 이루어진 자료구조, "서로소 집합"이라고 이해하면 될 것 같다.
Union-Find
union-find는 disjoint set의 표현 및 연산에 사용하는 알고리즘이다. 보통 Directed Tree를 이용해 구현하며, tree의 root는 해당 set의 대표값으로 생각하면 된다. 아래 예시에서는 {1, 2, 3, 4,}, {5, 6, 7, 8}, {9}가 각각의 set이며, 첫 번째 set의 대표값은 4, 두 번째 set의 대표값은 5, 세 번째 set의 대표값은 9이며 이 값들을 tree의 root로 생각하겠다는 것이다.
이렇게 설정했을 때 아래 3가지의 연산이 존재한다.
- makeset(x) : x를 포함하는 새로운 set을 만든다.
- find(x) : x가 속해있는 set의 root를 리턴한다.
- union(x, y) : x가 속해있는 set과 y가 속해있는 set을 하나로 합친다.
tree로 구현하는 이유를 생각해 보자. tree로 구현하면 find(x) 함수는 O(x가 속한 tree의 height), union 함수는 O(x가 속한 tree의 height + y가 속한 tree의 height)이다. 반면 배열로 구현할 경우 find(x)는 O(1)이지만 union 함수가 O(n)이 된다. union-find의 특성상 union(x, y)를 많이 사용하기 때문에 tree로 구현하는 것이 더 효율적이며, 추후 path compression을 사용하면 tree가 월등히 더 빨라진다.
또한, tree를 이용할 경우 tree의 root를 해당 set의 대표값으로 이용한다는 생각에서 나온 것이 union-find를 tree로 이용한다는 접근이다.
Pseudo Code
procedure makeset(s)
parent(x) = x
rank(x) = 0
procedure find(x)
while x != parent(x) :
x = parent(x)
end while
return x
procedure union(x, y)
rx = find(x)
ry = find(y)
if rx == ry :
return
end if
if rank(rx) < rank(ry) :
parent(rx) = ry
end if
else :
parent(ry) = rx
if rank(rx) == rank(ry) :
rank(rx) = rank(rx) + 1
end if
end else 위 pseudo code에는 앞에서 말하지 않은 rank라는 함수가 있다. rank(x)는 최적화를 위해 들어간 함수이며 x가 속해있는 set(subtree)의 height를 리턴한다. 그렇다면 rank(x)가 어떻게 최적화를 할까?
union(x, y)에서 보면 rank가 더 작은 것을 rank가 더 큰 것에 합병시킨다. 만약 rank가 같다면 합치고 기존 rank에 1을 더해준다. 돌려 말하자면, height가 더 작은 tree를 height가 더 큰 tree에 merge시키는 것이다. 이렇게 하지 않으면 tree height가 worst O(n-1)이 될 수 있기 때문에 이런 방법을 추가한다.
Property of Union-Find
root가 아닌 x에 대해 rank(x) < rank(parent(x))이다.
- 자명하다. parent의 height가 더 클 것이다.
x가 root가 아니면 rank(x)는 불변이다.
- rank(x)가 바뀌는 경우는 union(x, y)를 할 때 뿐이며, 그마저도 root의 rank만 변경한다. 즉, child node의 rank는 변하지 않는다.
rank가 k인 모든 root node의 subtree에는 적어도 2^k개의 node가 있다.
- induction으로 증명. k=0에서 1개의 node가 있다.
- k-1에서 성립 가정, rank k인 node는 rank k-1개 2개를 합쳐야 만들 수 있다. rank k-1인 각각의 subtree는 2^(k-1)개의 node를 가지므로 2 * 2^(k-1) = 2^k이므로 성립이다.
총 n개의 node가 있을 때 rank k인 node는 최대 n/(2^k)개 존재한다.
즉 max rank는 logn이기 때문에 tree height <= logn이다.
- 바로 위의 property로부터 유도된다.
- 즉슨, tree height가 logn보다 작거나 같기 때문에 union(x, y)와 find(x)의 시간복잡도가 O(logn)이다.
2. Path Compression
union(x, y)와 find(x)의 시간복잡도는 tree height에 비례하기 때문에 tree height를 짧게 유지하면 더 좋은 성능의 알고리즘을 만들 수 있다. 그 방법을 path compression이라 부르고 find(x)를 할 때 찾아지는 모든 node를 root 바로 밑에 붙일 것이다.
procedure find(x) :
if x == parent(x) :
return x
end if
else :
parent(x) = find(parent(x)) // x의 parent를 x의 root로 변경
end else
return parent(x)
Property of Union-Find After Path Compression
root가 아닌 x에 대해 rank(x) < rank(parent(x))이다.
- 자명하다. parent의 height가 더 클 것이다.
x가 root가 아니면 rank(x)는 불변이다.
- rank(x)가 바뀌는 경우는 union(x, y)를 할 때 뿐이며, 그마저도 root의 rank만 변경한다. 즉, child node의 rank는 변하지 않는다.
rank가 k인 모든 root node의 subtree에는 적어도 2^k개의 node가 있다.
- induction으로 증명. k=0에서 1개의 node가 있다.
- k-1에서 성립 가정, rank k인 node는 rank k-1개 2개를 합쳐야 만들 수 있다. rank k-1인 각각의 subtree는 2^(k-1)개의 node를 가지므로 2 * 2^(k-1) = 2^k이므로 성립이다.
총 n개의 node가 있을 때 rank k인 node는 최대 n/(2^k)개 존재한다.
즉 max rank는 logn이기 때문에 tree height <= logn이다.
바로 위의 property로부터 유도된다.즉슨, tree height가 logn보다 작거나 같기 때문에 union(x, y)와 find(x)의 시간복잡도가 O(logn)이다.
아래 2개의 property는 사라진다.
Time Complexity
path compression 이후 시간복잡도를 계산해 보자. 이를 위해 log*n이라는 새 수를 정의하자. log*n은 n을 1까지 끌어내리는 데 필요한 log 연산의 개수이다.
$\log ^*n\begin{cases}0&if\ n\ \le \ 1\\1+\log ^*\left(\log _2n\right)&if\ n\ >\ 1\end{cases}$
0보다 크거나 같은 정수 k에 대해 $0 <= rank(x) <= log n$인 각각의 rank는 {k+1, k+2, ... , $2^{k}$}의 형태를 가진다.
k = 0일 때 {1}
k = 1일 때 {2}
k = 2일 때 {3, 4}
k = 4일 때 {5, 6, ... , 16}
k = 16일 때 {17, 18, ... , $2^{16}$}
k = $2^{16}$ (= 65536)일 때 {65537, 65538, ... , $2^{65536}$}
, ...
이제 edge를 아래와 같이 분류해 보자.
type-1 edge는 다른 group 사이의 edge, type-2 edge는 같은 group의 edge이다. 그러면 union(x, y)와 find(x)를 m번 호출한다고 했을 때
전체 edge 수
= type 1 edge(find m번으로 지워지는 type 1 edge 개수 == worst log*n)
+ sum of (x에 인접한 type-2 edge)
= sum of(m번의 find call로 불러진 type-1 edge) + sum of (x에 인접한 type-2 edge)
= O(m log*n) + sum of (x에 인접한 type-2 edge)
이다.
sum of (x에 인접한 type-2 edge)를 조금 자세히 구해보자. 모든 subtree의 element 개수의 상한은 2^k이다. rank k인 node 수는 property에 의해 n/(2^k)이므로 O(n log*n)이다.
보통 vertex보다 edge 수가 더 많으므로 O(m log*n)이 된다.
∴ m번의 find(x), union(x, y) 연산에 걸리는 시간은 O(m log*n)이다.
1번의 연산에 걸리는 평균 시간이 O(log*n)이다.
소스코드 : O(log*n)
제일 중요한 구현 방법이다. 다만 유의할 점, c++에서 find와 union, parent과 rank 이미 사용되고 있는 함수/변수이므로 앞의 것을 대문자로 바꿔 사용하자.
int Parent[1000001];
int Rank[1000001];
void Makeset(int s){
Parent[s] = s;
Rank[s] = 0;
return;
}
int Find(int x){
if(x == Parent[x]) return x;
Parent[x] = Find(Parent[x]); // x의 parent를 x의 root로 설정
return Parent[x];
}
void Union(int x, int y){
int rx = Find(x);
int ry = Find(y);
if(rx == ry) return;
if(Rank[rx] < Rank[ry]) // ry의 height가 더 크면 rx가 밑으로 글어가야 함
Parent[rx] = ry;
else{ // 그렇지 않다면 ry가 밑으로 들어가야 함
Parent[ry] = rx;
if(Rank[rx] == Rank[ry]){ // rank가 같으면 rank 조절
Rank[rx]++;
}
}
}