유니온-파인드(Union-Find)
dev/algorism2017. 8. 25. 21:42
● 정의
유니온-파인드(Union-Find) 자료구조 (혹은 Disjoint-Set 자료구조)는 교집합이 존재하지 않는 상호 배타적인 부분집합들로 나누어진 원소들에 대한 정보를 가진 자료구조
● 설명
자료구조에서 제공하는 연산은 두 가지
1. Group (Find) : 어떤 원소가 어느 집합에 속해 있는지를 알려주는 연산
2. Join (Union) : 두 개의 부분집합을 하나의 집합으로 합치는 연산. 즉, 두 개의 원소를 입력으로 주면 그 두 원소가 서로 다른 집합에 속할 경우 그 집합을 하나로 합침
● 예시
시간 복잡도를 대폭 개선하여 가장 널리 사용하고 있는 경로 압축 (Path Compression) 을 이용한 구현법을 소개
초기의 Set 배열 변수는 모두 0 으로 초기화되어 있다고 가정
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | // UnionFind.cppconst int _M_size_ = 1000; // max number of elements int Set[_M_size_ + 1]; // starts with 1. index 0 is not used. int group(int n) { if (!Set[n]) return n; return Set[n] = group(Set[n]); // path compression } void join(int a, int b) { int A(group(a)), B(group(b)); if (A != B) Set[A] = B;} |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | // UnionFind.java class UnionFind { // max number of elements static final int _M_size_ = 1000; // starts with 1, index 0 is not used. static int Set[] = new int[_M_size_ + 1]; static int group(int n) { if(Set[n] == 0) return n; return Set[n] = group(Set[n]); // path compression } static void join(int a, int b) { int A = group(a), B = group(b); if (A != B) Set[A] = B; } |
