Union-Find 란? #

공통원소가 없는 상호배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 Disjoint Set을 표현할 때 사용하는 자료구조이다.
어떤 노드가 다른 노드와 연결되어 있는지를 판별하는 알고리즘으로써 2logN 포인터만 따라가면 p-q 연결성을 확인할 수 있다.

이미지출처: <http://vancexu.github.io/2015/07/13/intro-to-union-find-data-structure.html>

지원연산 #

Quick-find solution #

M 유니언 연산과 N 노드가 있을 때 MN 연산으로 연결성을 판별하는 알고리즘

Quick-union solution #

M > N 일때 MN/2 연산으로 연결성을 판별하는 알고리즘

Weighted quick union #

N 노드가 있을 때 2lgN 수행시간을 보여주는 알고리즘

활용 #

구현이 간단하고 동작속도가 빠르기 때문에 다른 알고리즘의 일부로 사용된다.

• 그래프의 연결성 확인
• 가장 큰 집합 추적
• 픽셀들을 객체로 간주 한 사진 파일, 사람을 객체로 간주한 소셜 네트워크, 회로 요소를 객체로 간주 한 컴퓨터 칩 등 동적 연결성(dynamic connectivity) 확인

Suggested Pages #

• 0.025 Complexity
• More suggestions...