[알고리즘] Union-Find (자바 / Java)

이태권 (Taekwon Lee)·2023년 1월 6일

Algorithms Union Find 알고리즘 자료구조

[알고리즘] 이론

목록 보기

1/3

(1) Dynamic Connectivity

N개의 객체(objects)가 있을 때
Union Command라는 것은 두 객체를 연결시키는 것이다(connect two objects)
find/connected query → 두 객체 사이를 연결하는 경로(path)가 있는가?
- 직접적인 연결이 아니더라도, 간접적으로 연결이 되어 있는가?

객체 모델링

각 객체의 이름을 숫자로 붙인다
(When programming, it’s convenient to name objects $0$ to $N-1$ )

각 객체를 나타내는 정수를 배열의 인덱스로 사용할 수 있다(use integers as array index.)
union-find 알고리즘과 관련이 없는 수많은 details를 숨길 수 있다.(suppress details not relevant to untion-find)
객체의 이름을 숫자로 매핑(mapping; 사상)하여 추후에 심볼 테이블이나 검색 알고리즘에도 적용할 수 있다.

연결 모델링

A와 B가 ‘연결 되어 있다’라는 말은 동치 관계(equivalence relation)임을 가정한다.

이 표현은 반사적(반사율, reflexive)이다.
- p는 p에 연결되어 있다.
이 표현은 대칭적(대칭률, symmetric)이다.
- p는 q에 연결되어 있으면, q 또한 p에 연결되어 있다.
이 표현은 이행적(移行; 이행률, transitive)이다.
- p는 q에 연결되어 있고 q가 r에 연결되어 있으면, p는 r에 연결되어 있다.

연결된 요소(Connected components)는 상호 연결된 객체들의 최대 집합(maximal set)이다.

연결 요소 중 어느 두 객체가 서로 연결되어 있고 그 두 객체와 연결되어 있는 외부의 객체가 없다면, 이를 연결된 요소라 한다. (these components have the property that if any two objects in them are connected and there is no object outside that is connected to those objects, that's connected components.)

명령어 구현

find query

두 객체가 동일한 연결된 요소에 있는지를 확인
(to check if two objects are in the same component)

union command

두 객체를 포함하는 연결 요소의 합집합으로 연결 요소를 대체함
(to replace components containing two objects with their union)

union(2,5)를 통해 연결된 요소가 하나 줄어듦

구현해야 할 코드

public class UF                 // UF for union find


UF (int N)                      // union-find 자료구조를 N개의 객체(0 to N - 1)로 초기화
void union(int p, int q)        // p와 q 사이에 연결 추가
boolean connected(intp, int q)  // p와 q가 같은 요소인가? -> boolean 자료형으로 반환
int find(int p)                 // p(0 to N - 1)에 대한 연결 식별자
int count()                     // 전체 요소의 개수를 반환