Union-find 알고리즘 (Disjoint Set), 서로소 집합

Disjoint Set이란?

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

상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조라고 생각하면 된다.

흔히 서로소 집합 자료구조 라고도 한다. 

 

 

Union-Find 란?

Union-Find는 서로소 집합을 표현할 때 사용하는 알고리즘이다.

집합을 표현하는 방법으로는 배열, 연결리스트 등을 이용할 수 있다. 그 중 가장 효율적인 트리 구조를 이용하여 구현한다. 

보통 MST의 크루스칼 알고리즘에서 사용된다. 

트리를 이용한 집합의 처리
- 같은 집합의 원소들은 하나의 트리로 관리한다. (자식 노드가 부모 노드를 가리킴)
- 트리의 루트를 집합의 대표 원소로 삼는다. 

 

 

Union-Find 연산

1. Make-Set(x) : 원소 x로만 이루어진 집합을 만든다.  - 초기화 
2. Find-Set(x) : 원소 x를 가지고 있는 집합을 알아낸다. (찾는다)  - 찾기
3. Union(x, y) : 원소 x를 가진 집합과 원소 y를 가진 집합의 합집합  - 합하기

 

 

트리를 이용한 집합 처리 알고리즘 

Make-Set(x) 
{
	p[x] = x;
}

Union(x, y)
{
	p[Find-Set(y)] = Find-Set(x);
}

Find-Set(x)
{
	if(x=p[x])
    	then return x;
        else return Find-Set(p[x]);
}

 

 

Union-Find 과정 

 

 

Union-Find 기본 코드

parents = [i for i in range(SIZE)]


def find(parent, x):
    if parent[x] == x:
        return x

    else:	#부모 찾기 
        return find(parent, parent[x])


def union(parent, x, y):
    # 각 원소가 속한 트리의 루트 노드를 찾기.
    fX = find(parent, x)
    fY = find(parent, y)

    parent[fY] = fX

 

 

Union-Find 연산 효율 높이는 방법

랭크를 이용한 Union

- 각 노드는 자신을 루트로 하는 서브트리의 높이를 랭크 Rank 라는 이름으로 저장한다. 

- 두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다. 

 

경로 압축

- Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 루트를 가리키도록 포인터를 바꾼다. 

 

 

 

2023.04.04 - [📚 Algorithm/Algorithm Note] - 알고리즘 - 최소 신장 트리(Minimum Spanning Tree), 크루스칼(Kruskal), 프림(Prim) Python 코드