Union - Find 알고리즘(서로소 집합)

Union - Find 알고리즘(서로소 집합)

서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들.

즉, 교집합이 없다.

Union - Find 알고리즘은 대표자를 정해 특정 멤버가 대표하여 각 집합을 구분한다.

Union - Find 알고리즘의 집합연산 세가지

Make - Set(x) : 각 원소를 대표자로 하는 집합 만들기 Find - Set(x) : x가 속한 그룹의 대표자 찾기 Union(x, y) : x가 속한 그룹과 y가 속한 그룹을 합치기.. 이때 Find - Set을 이용해 대표자를 찾아 비교하여 소속그룹인지 확인한다.

연산의 효율을 높이기 위한 방법

Rank를 이용한 Union

각 노드는 자신을 루트로 하는 subtree의 높이를 랭크(Rank)라는 이름으로 저장. 두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다. (랭크 변화를 없도록 하는 것을 의미 --> 랭크관리가 필요하다)

Path compression (압축)

: Find - Set을 하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 한다.(Find - Set을 이용해 대표자를 찾아 비교하여 소속그룹인지 확인)

from http://elevensix.tistory.com/56 by ccl(A) rewrite - 2021-08-24 14:26:12