data-structures
유니온 - 찾기 데이터 구조
수색…
소개
union-find (또는 disjoint-set) 데이터 구조는 여러 개의 요소를 분리 된 집합으로 분할하는 단순한 데이터 구조입니다. 모든 세트에는 다른 세트와 구별하는 데 사용할 수있는 대표가 있습니다.
이것은 많은 알고리즘에서 사용됩니다. 예를 들어, Kruskal의 알고리즘을 통해 최소 스패닝 트리를 계산하고, 연결되지 않은 그래프 등으로 연결된 구성 요소를 계산하는 데 사용됩니다.
이론
Union 찾기 데이터 구조는 다음 작업을 제공합니다.
-
make_sets(n)
은n
싱글 톤으로 유니온 찾기 데이터 구조를 초기화합니다. -
find(i)
는 요소i
의 집합에 대한 대표를 반환합니다. -
union(i,j)
는i
와j
포함하는 집합을 병합합니다.
우리는 우리의 요소 분할 나타내는 0
행 n - 1
부모 요소에 저장하여 parent[i]
각 요소 i
결국 포함하는 집합의 대표 리드 i
.
요소 자체가 대표 인 경우, 그 자체의 부모, 즉 parent[i] == i
입니다.
따라서 싱글 톤 세트로 시작하면 모든 요소가 자체 대표입니다.
이 부모 포인터를 따라 간단하게 주어진 집합에 대한 대표자를 찾을 수 있습니다.
세트를 어떻게 병합 할 수 있는지 보자.
요소 0과 1, 요소 2와 3을 병합하려면 0의 부모를 1로 설정하고 2의 부모를 3으로 설정하여이 작업을 수행 할 수 있습니다.
이 간단한 경우 요소 부모 포인터 자체 만 변경해야합니다.
병합 (0.3), 우리는 세트의 대표의 부모를 설정 한 후 : 우리는 그러나 더 큰 세트를 병합 할 경우, 우리는 항상 다른 세트로 병합 될 세트의 대표의 부모 포인터를 변경해야합니다 3을 포함하는 세트의 대표에 0을 포함
예제를 좀 더 흥미롭게 만들려면 (4,5), (5,6) 및 (3,4)를 병합 해 봅시다.
소개하고자하는 마지막 개념은 경로 압축입니다 .
세트의 대표자를 찾고 싶다면 대표자를 만나기 전에 여러 개의 상위 포인터를 따라야 할 수도 있습니다. 각 세트의 담당자를 상위 노드에 직접 저장하여이 작업을보다 쉽게 수행 할 수 있습니다. 우리는 요소를 병합 한 순서를 잃어 버리지 만, 잠재적으로 큰 런타임 이득을 가질 수 있습니다. 우리의 경우, 압축되지 않은 경로는 0, 4 및 5에서 3까지의 경로입니다.
기본 구현
유니온 찾기 데이터 구조의 가장 기본적인 구현은 구조의 모든 요소에 대한 부모 요소를 저장하는 배열 parent
로 구성됩니다. 요소 i
대한 이러한 부모 '포인터'다음에 parent[j] = j
가있는 i
포함하는 집합의 대표 j = find(i)
로 연결됩니다.
using std::size_t;
class union_find {
private:
std::vector<size_t> parent; // Parent for every node
public:
union_find(size_t n) : parent(n) {
for (size_t i = 0; i < n; ++i)
parent[i] = i; // Every element is its own representative
}
size_t find(size_t i) const {
if (parent[i] == i) // If we already have a representative
return i; // return it
return find(parent[i]); // otherwise return the parent's representative
}
void merge(size_t i, size_t j) {
size_t pi = find(i);
size_t pj = find(j);
if (pi != pj) { // If the elements are not in the same set:
parent[pi] = pj; // Join the sets by marking pj as pi's parent
}
}
};
개선 사항 : 경로 압축
유니온 찾기 데이터 구조에서 많은 merge
연산을 수행하면 parent
포인터로 표현되는 경로가 상당히 길어질 수 있습니다. 이론 부분에 이미 설명 된대로 경로 압축 은이 문제를 완화하는 간단한 방법입니다.
매 k 번째 병합 작업이나 유사한 작업을 수행 한 후에 전체 데이터 구조에 대한 경로 압축을 시도 할 수도 있지만 이러한 작업에는 매우 큰 런타임이 필요할 수 있습니다.
따라서 경로 압축은 대부분 구조의 작은 부분, 특히 집합의 대표자를 찾기 위해 걷는 경로에서만 사용됩니다. 이것은 재귀 subcall마다 find
연산의 결과를 저장하여 수행 할 수 있습니다.
size_t find(size_t i) const {
if (parent[i] == i) // If we already have a representative
return i; // return it
parent[i] = find(parent[i]); // path-compress on the way to the representative
return parent[i]; // and return it
}
개선 사항 : 크기별 조합
merge
의 현재 구현에서 세트의 크기를 고려하지 않고 항상 왼쪽 세트를 오른쪽 세트의 하위로 선택합니다. 이 제한이 없으면 요소에서 해당 대표로의 경로 압축 ( 경로 압축 없음 )이 상당히 길어서 find
호출시 큰 런타임이 발생할 수 있습니다.
또 다른 공통된 개선점은 사이즈 휴리스틱에 의한 조합입니다. 정확히 말하면 다음과 같습니다 : 두 세트를 병합 할 때 항상 더 큰 세트를 더 작은 세트의 부모로 설정하여 최대 길이의 경로를 유도합니다 단계 :
클래스에 추가 구성원 std::vector<size_t> size
를 저장합니다.이 std::vector<size_t> size
는 모든 요소에 대해 1로 초기화됩니다. 두 세트를 병합 할 때 더 큰 세트는 더 작은 세트의 부모가되며 우리는 두 가지 크기를 합산합니다.
private:
...
std::vector<size_t> size;
public:
union_find(size_t n) : parent(n), size(n, 1) { ... }
...
void merge(size_t i, size_t j) {
size_t pi = find(i);
size_t pj = find(j);
if (pi == pj) { // If the elements are in the same set:
return; // do nothing
}
if (size[pi] > size[pj]) { // Swap representatives such that pj
std::swap(pi, pj); // represents the larger set
}
parent[pi] = pj; // attach the smaller set to the larger one
size[pj] += size[pi]; // update the size of the larger set
}
개선 사항 : 순위 별 조합
크기에 따라 결합 대신에 일반적으로 사용되는 또 다른 발견 적 방법은 순위 지능적 방법에 의한 결합입니다
기본 아이디어는 실제로 세트의 정확한 크기를 저장할 필요가 없다는 것입니다. 크기에 대한 근사치 (이 경우 : 대략 세트의 크기의 대수)는 크기에 따라 합집합과 동일한 속도를 달성하기에 충분합니다.
이를 위해 다음과 같이 주어진 집합의 순위 개념을 소개합니다.
- 싱글 톤은 순위 0을가집니다.
- 동일하지 않은 순위를 가진 두 세트가 병합되면 순위가 변경되지 않은 채 큰 순위의 세트가 상위가됩니다.
- 동일한 순위의 두 세트가 병합되면, 그 중 하나는 다른 것의 부모가됩니다 (선택은 임의적 일 수 있음). 순위가 증가합니다.
순위 에 의한 조합의 한 가지 이점은 공간 사용입니다. 최대 순위가 대략 좋아지면 모든 실제 입력 크기에 대해 순위는 1 바이트로 저장할 수 있습니다 (
n < 2^255
).
순위에 의한 조합의 간단한 구현은 다음과 같이 보일 수 있습니다 :
private:
...
std::vector<unsigned char> rank;
public:
union_find(size_t n) : parent(n), rank(n, 0) { ... }
...
void merge(size_t i, size_t j) {
size_t pi = find(i);
size_t pj = find(j);
if (pi == pj) {
return;
}
if (rank[pi] < rank[pj]) {
// link the smaller group to the larger one
parent[pi] = pj;
} else if (rank[pi] > rank[pj]) {
// link the smaller group to the larger one
parent[pj] = pi;
} else {
// equal rank: link arbitrarily and increase rank
parent[pj] = pi;
++rank[pi];
}
}
최종 개선 : 아웃 오브 바운드 저장소가있는 순위 별 조합
경로 압축과 함께, 순위에 의한 결합은 거의 union-find 데이터 구조에 대해 일정한 시간 연산을 거의 달성 합니다만, 범위 밖의 항목에 rank
저장함으로써 rank
저장을 완전히 제거 할 수있는 마지막 트릭이 있습니다. parent
배열 그것은 다음과 같은 관찰에 근거합니다 :
- 우리는 실제로 다른 요소가 아닌 대표자 의 순위 만 저장하면됩니다. 이 담당자들에게는
parent
를 저장할 필요가 없습니다. - 지금까지,
parent[i]
는 최대size - 1
. 즉, 더 큰 값은 사용되지 않습니다. - 모든 등급은 최대입니다.
.
이것은 우리에게 다음과 같은 접근 방식을 제공합니다 :
- 조건
parent[i] == i
대신에 이제 우리는
parent[i] >= size
- 이 out-of-bounds 값을 사용하여 집합의 순위를 저장합니다. 즉, 대표
i
가있는 집합은 rankparent[i] - size
- 따라서 우리는
parent[i] = i
대신parent[i] = size
부모 배열을 초기화합니다.parent[i] = i
, 각 집합은 순위 0을 가진 자체 대표입니다.
우리는 size
값에 의해서만 순위 값을 상쇄하기 때문에 merge
의 구현에서 parent
벡터로 rank
벡터를 간단히 대체 할 수 있으며 find
에서 대리인을 식별하는 조건을 교환하면됩니다.
순위 및 경로 압축에 의한 통합을 사용하여 구현 완료 :
using std::size_t;
class union_find {
private:
std::vector<size_t> parent;
public:
union_find(size_t n) : parent(n, n) {} // initialize with parent[i] = n
size_t find(size_t i) const {
if (parent[i] >= parent.size()) // If we already have a representative
return i; // return it
return find(parent[i]); // otherwise return the parent's repr.
}
void merge(size_t i, size_t j) {
size_t pi = find(i);
size_t pj = find(j);
if (pi == pj) {
return;
}
if (parent[pi] < parent[pj]) {
// link the smaller group to the larger one
parent[pi] = pj;
} else if (parent[pi] > parent[pj]) {
// link the smaller group to the larger one
parent[pj] = pi;
} else {
// equal rank: link arbitrarily and increase rank
parent[pj] = pi;
++parent[pi];
}
}
};