data-structures
ユニオン検索データ構造

前書き

理論

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回目のマージ操作またはそれに類する操作のたびに、データ構造全体のパス圧縮を試みる可能性がありますが、このような操作では実行時間が非常に長くなる可能性があります。

したがって、パス圧縮は、ほとんどの場合、構造の小さな部分、特に集合の代表を見つけるために歩く経路上でのみ使用されます。これは、すべての再帰サブコールの後に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呼び出しで大きなランタイムが発生しfind 。

もう一つの一般的な改良点はサイズヒューリスティックによる組合であり、それは正確に言う通りです：2つの集合をマージするとき、より大きな集合を常に小さな集合の親とすることで、 ステップ：

追加のメンバーstd::vector<size_t> sizeクラスに格納します。クラスのstd::vector<size_t> sizeはすべての要素に対して1に初期化されます。 2つのセットをマージすると、大きなセットは小さなセットの親になり、2つのサイズを合計します。

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
    }

改善：ランクごとの連合

unionの代わりにsizeで一般的に使用される別のヒューリスティックは、 rank by heuristic

その基本的な考え方は、実際にはセットの正確なサイズを格納する必要はないということです。サイズの近似値（この場合、おおよそセットのサイズの対数）は、ユニオンのサイズと同じ速度を達成するのに十分です。

このために、集合の階数の概念を導入します。これは次のように与えられます。

• シングルトンはランク0
• 等しくないランクの2つのセットがマージされた場合、ランクが大きいままのセットは親になり、ランクは変更されません。
• 等しいランクの2つのセットがマージされている場合、それらの1つがもう一方の親になります（選択は任意です）。そのランクは増分されます。

ランクごとのユニオンの利点の1つは、スペースの使用です。最大ランクが概ね現実的なすべての入力サイズに対して、ランクは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];
        }
    }

最終的な改善：アウト・オブ・バウンド・ストレージ

パス圧縮と組み合わせると、ランクごとのユニオンは、ユニオン・ファインド・データ構造上でほぼ一定の時間操作をほぼ達成するが、最終的なトリックがあるので、 rankストレージを完全に取り除くことができる。 parent配列これは、以下の観察に基づいています。

• 実際には、他の要素ではなく、 代理人のランクを格納するだけで済みます。これらの代理人には、 parentを保管する必要はありません。
• 今のところ、 parent[i]は最大size - 1です。つまり、大きな値は未使用です。
• すべての順位は最大です 。

これは、次のアプローチに私たちをもたらします：

• parent[i] == iという条件の代わりに、
  parent[i] >= size
• これらの範囲外の値を使用して、セットのランクを格納します。つまり、代表iのセットは、rank parent[i] - size
• したがって、 parent[i] = i代わりにparent[i] = i parent[i] = size使用して親配列を初期化します。つまり、各セットはランク0の独自の代表です。

ランク値はsizeだけをオフセットするので、 mergeの実装ではrankベクトルをparentベクトルで置き換えるだけで、 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];
        }
    }
};