- 서로소 집합(disjoint sets)란 공통 원소가 없는 두 집합을 의미
- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
- 합집합(Union) : 두개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
- 찾기 (find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
- click
- 합집합(Union) 연산을 확인하여 서로 연결된 두 노드 A,B를 확인
- A와 B의 루트노드 A', B'를 각각 찾는다
- A'를 B'의 부모 노드로 설정한다
- 모든 합집합(Union) 연산을 처리할 때까지 1번의 과정을 반복
parent = new int[V+1];
for (int i = 1; i <= V; i++) {
parent[i] = i; // 자기자신 가리키기
}
- parent[x] = y; // x번 노드의 부모는 y노드 라는 의미
- 합집합 연산이 편향되게 이루어지는 경우 찾기 함수가 비효율적으로 동작 (최악 O(V))
- 경로 압축(Path Compression) 을 이용, 부모 테이블 값을 바로 갱신
public static int find (int x) {
if (x == parent[x]) {
return x;
} else {
return parent[x] = find(parent[x]); // 부모값이 루트가 될 수 있도록
}
}
- 더 큰 노드가 작은 노드를 가리키는 것이 관행 (1)<-(4)
public static void union (int x, int y) {
x = find(x);
y = find(y);
// 더 큰 노드가 작은 노드를 가리키는 것이 관행
if (x < y) {
parent[y] = x;
} else {
parent[x] = y;
}
/*
// 간단히 표현
if (x != y) {
parent[y] = x;
}
*/
}