수색…


소개

union-find (또는 disjoint-set) 데이터 구조는 여러 개의 요소를 분리 된 집합으로 분할하는 단순한 데이터 구조입니다. 모든 세트에는 다른 세트와 구별하는 데 사용할 수있는 대표가 있습니다.

이것은 많은 알고리즘에서 사용됩니다. 예를 들어, Kruskal의 알고리즘을 통해 최소 스패닝 트리를 계산하고, 연결되지 않은 그래프 등으로 연결된 구성 요소를 계산하는 데 사용됩니다.

이론

Union 찾기 데이터 구조는 다음 작업을 제공합니다.

  • make_sets(n)n 싱글 톤으로 유니온 찾기 데이터 구조를 초기화합니다.
  • find(i) 는 요소 i 의 집합에 대한 대표를 반환합니다.
  • union(i,j)ij 포함하는 집합을 병합합니다.

우리는 우리의 요소 분할 나타내는 0n - 1 부모 요소에 저장하여 parent[i] 각 요소 i 결국 포함하는 집합의 대표 리드 i .
요소 자체가 대표 인 경우, 그 자체의 부모, 즉 parent[i] == i 입니다.

따라서 싱글 톤 세트로 시작하면 모든 요소가 자체 대표입니다.

싱글 톤 세트 : 모든 요소는 자체 부모입니다.

이 부모 포인터를 따라 간단하게 주어진 집합에 대한 대표자를 찾을 수 있습니다.

세트를 어떻게 병합 할 수 있는지 보자.
요소 0과 1, 요소 2와 3을 병합하려면 0의 부모를 1로 설정하고 2의 부모를 3으로 설정하여이 작업을 수행 할 수 있습니다.

병합 (0,1), 병합 (2,3)

이 간단한 경우 요소 부모 포인터 자체 만 변경해야합니다.
병합 (0.3), 우리는 세트의 대표의 부모를 설정 한 후 : 우리는 그러나 더 큰 세트를 병합 할 경우, 우리는 항상 다른 세트로 병합 될 세트의 대표의 부모 포인터를 변경해야합니다 3을 포함하는 세트의 대표에 0을 포함

병합 후 (0,3)

예제를 좀 더 흥미롭게 만들려면 (4,5), (5,6) 및 (3,4)를 병합 해 봅시다.

병합 (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 호출시 큰 런타임이 발생할 수 있습니다.

또 다른 공통된 개선점은 사이즈 휴리스틱에 의한 조합입니다. 정확히 말하면 다음과 같습니다 : 두 세트를 병합 할 때 항상 더 큰 세트를 더 작은 세트의 부모로 설정하여 최대 길이의 경로를 유도합니다 로그 n 단계 :

클래스에 추가 구성원 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을가집니다.
  • 동일하지 않은 순위를 가진 두 세트가 병합되면 순위가 변경되지 않은 채 큰 순위의 세트가 상위가됩니다.
  • 동일한 순위의 두 세트가 병합되면, 그 중 하나는 다른 것의 부모가됩니다 (선택은 임의적 일 수 있음). 순위가 증가합니다.

순위의한 조합의 한 가지 이점은 공간 사용입니다. 최대 순위가 대략 좋아지면 로그 n 모든 실제 입력 크기에 대해 순위는 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 . 즉, 더 큰 값은 사용되지 않습니다.
  • 모든 등급은 최대입니다. 로그 n .

이것은 우리에게 다음과 같은 접근 방식을 제공합니다 :

  • 조건 parent[i] == i 대신에 이제 우리는
    parent[i] >= size
  • 이 out-of-bounds 값을 사용하여 집합의 순위를 저장합니다. 즉, 대표 i 가있는 집합은 rank parent[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];
        }
    }
};


Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow