[Algorithm] Union-Find algorithm

Disjoint Set

- 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조

즉, 공통 원소가 없는 "상호 배타적"인 부분 집합들로 나눠진 원소들에 대한 자료구조

 

Union-Find algorithm

- 서로소 집합(Disjoint Set)을 표현할 때 사용하는 알고리즘

- 그래프 알고리즘으로 Union(합집합) + Find(찾기) 로 '합집합 찾기'라는 의미를 가지고 있다.

- 여러 노드 중 2개의 노드를 선택하여 같은 그래프에 속해 있는 지 확인하는 알고리즘이다.

 

 

연산

- Make-set(x) // 초기화

  : x를 유일한 원소로 하는 새로운 집합 생성

- Union(x, y) // 합하기

  :원소 x가 속한 부분집합과 원소 y가 속한 부분집합의 합집합을 구한다.

  각 부분집합은 트리로 나타낸다.

- Find(x)  //찾기

  : x가 속한 집합의 대표 값(루트 노드 값)을 반환한다. x가 어떤 집합에 속해 있는지 찾는 연산

 

 

구현(배열 이용)

- 노드의 개수 만큼 배열 선언

- 각 노드의 루트노드를 가르키는 배열 선언, 초기화(parent 배열)

- 주어진 조건에 맞게 각 노드의 parent 배열 값은 그 노드가 가르키는 노드로 변경

 

- Find(x) : 루트 노드를 찾는 함수이므로 루트에 도달할 때까지 부모 노드를 찾아 올라간다.

int find(int x) {
	if (parent[x] == x) return x;
	return parent[x] = find(parent[x]);
}

 

- Union(x) : x 및 y를 포함하는 부분집합을 나타내는 트리를 다른 것의 부트리로 만든다.

void merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x != y) parent[y] = x;
}

 

Union-Find

전체 집합이 있을 때 구성 원소들이 겹치지 않도록 분할하는데 자주 사용

- Kruskal MST알고리즘에서 새로 추가할 간선의 양끝 정점이 같은 집합에 속해 있는지 검사하는 경우 (사이클 형성 여부 확인)

- 초기에 {0}, {1}, {2}, … {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려는 경우

- 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 가입한 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하는 경우

 

p.s. 분할(Partition) 이란

- 임의의 집합을 분할한다는 것은 각 부분 집합이 아래의 두 가지 조건을 만족하는 Disjoint Set 이 되도록 쪼개는 것이다.
 1.분할된 부분 집합을 합치면 원래의 전체 집합이 된다.
 2.분할된 부분 집합끼리는 겹치는 원소가 없다.
- 예를 들어, S = {1, 2, 3, 4}, A = {1, 2}, B = {3, 4}, C = {2, 3, 4}, D = {4}라면
  1.A와 B는 S의 분할 O. A와 B는 Disjoint Set
  2.A와 C는 S의 분할 X. 겹치는 원소가 존재
  3.A와 D는 S의 분할 X. 두 집합을 합해도 S가 되지 않음

 

 

시간복잡도

평균적으로 트리의 높이만큼 탐색하게 되므로 시간 복잡도는 O(logn)이 된다.

최악의 경우로 경사 트리일때는 트리의 높이가 n이므로 시간복잡도는 O(n)이다.

 

Union-Find의 가중법칙

Union(x, y)연산에서 원소x와 y가 속한 부분집합에 대한 트리를 각각Tx, Ty라고 할때,

Tx의 노드 개수가 더 많으면 Ty의 루트를 Tx의 루트의 자식이,

그렇지 않으면 Tx의 루트를 Ty의 루트의 자식이 되도록 만든다.

→가중 법칙에 따라 구성된 트리의 높이는, 노드 개수르르 n이라고 할 때, log2 n을 넘지 않는다.

 

증명 : 수학적 귀납법으로 증명

▶ n = 1인 경우 h = 0 = log2 n 이므로 성립

▶ n >= 2, Ti의 노드 개수= ni, 높이= hi, n1>= n2 가정

▶ 그러면 h = max h1, h2 + 1이다.

▶ h1 <= log2 n1 <= log2 n

▶ h2 <= log2 n2 <= log2 n2 <= logn-1

▶따라서 h <= log2n이 성립

 

참고 자료

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html