Union-Find サイズの最適化

前のセクションの考え方に従い、下図のような Union-Find をunion(4,9)操作します。

マージ操作後の構造は次のようになります：

この構造では木の階層が比較的高いことがわかります。もし要素数が増えると、発生するコストは比較的大きくなります。この問題の解決はとても簡単で、具体的なポインタ操作を行う前に判断し、要素数の少ない集合のルートノードを要素数の多いルートノードに指し示すことで、より高い確率で階層の低い木を生成できます。

Union-Find を構築するときには、もう1つパラメータが必要です。sz配列、sz[i]表すのは、i「〜を根とする集合の要素数」。

// コンストラクタ
public UnionFind3(int count){
    parent = new int[count];
    sz = new int[count];
    this.count = count;
    // 初期化、各parent[i]は自分自身を指し、各要素が自分自身でひとつの集合を構成することを示します
    for( int i = 0 ; i < count ; i ++ ){
        parent[i] = i;
        sz[i] = 1;
    }
}

マージ操作を行うときは、2つの要素が属する木の要素数の違いに基づいてマージ方向を判断します。

public void unionElements(int p, int q){
    int pRoot = find(p);
    int qRoot = find(q);
    if( pRoot == qRoot )
        return;
    if( sz[pRoot] < sz[qRoot] ){
        parent[pRoot] = qRoot;
        sz[qRoot] += sz[pRoot];
    }
    else{
        parent[qRoot] = pRoot;
        sz[pRoot] += sz[qRoot];
    }
}

最適化後、マージ結果は次のようになり、9は親ノード8を指します。

Java サンプルコード

ソースコードパッケージのダウンロード：Download

UnionFind3.java ファイルコード：

package サンプル.union;

/**
* Union-Findのサイズ最適化
 */
public class UnionFind3 {
    // parent[i] は最初の要素が指す親ノードを表します
    private int[] parent;
    // sz[i] は i を根とする集合の要素数を表します
    private int[] sz;
    // データ数
    private int count;

    // コンストラクタ
    public UnionFind3(int count){
        parent = new int[count];
        sz = new int[count];
        this.count = count;
        // 初期化、各parent[i]は自分自身を指し、各要素が自分自身でひとつの集合を構成することを示します
        for( int i = 0 ; i < count ; i ++ ){
            parent[i] = i;
            sz[i] = 1;
        }
    }

    // 検索プロセス、要素pに対応する集合番号を検索します
    // O(h) 複雑度、h は木の高さ
    private int find(int p){
        assert( p >= 0 && p < count );
        // 自分の親ノードを繰り返し問い合わせ、ルートノードに到達するまで続けます
        // ルートノードの特徴: parent[p] == p
        while( p != parent[p] )
            p = parent[p];
        return p;
    }

    // 要素pと要素qが同じ集合に属するかどうかを確認します
    // O(h) 複雑度、h は木の高さ
    public boolean isConnected( int p , int q ){
        return find(p) == find(q);
    }

    // 要素pと要素qが属する集合をマージします
    // O(h) 複雑度、h は木の高さ
    public void unionElements(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if( pRoot == qRoot )
            return;
        // 2つの要素が属する木の要素数の違いに基づいて、マージ方向を判断します
        // 要素数が少ない集合を、要素数が多い集合にマージします
        if( sz[pRoot] < sz[qRoot] ){
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }
        else{
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }
}
その他の拡張