Union-Find rank の最適化

前の節では Union-Find の size に基づく最適化を紹介しましたが、特定のシナリオでは問題が発生する場合もあります。下図のように、union(4,2) を実行します。

前の節の size の最適化に従うと、要素が少ない集合のルートノードが要素が多い集合のルートノードを指します。操作後、深さは 4 になり、以前より 1 層増えました。下図のようになります。

このことから、集合の size に基づく方向の判断は完全に正しいわけではないことがわかります。より正確には、2 つの集合の深さに基づいてルートノードの向きを具体的に判断します。深さが浅い集合のルートノードが、深さが深い集合のルートノードを指します。下図のようになります。これが rank に基づく最適化です。

Union-Find の属性に rank 配列を追加します。rank[i] は、i をルートとする集合が表す木の深さを示します。

...
private int[] rank;   // rank[i]は、iをルートとする集合が表す木の深さを示します
private int[] parent; // parent[i]は、i番目の要素が指す親ノードを示します
private int count;    // データ数
...

コンストラクタをそれに応じて修正します：

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

2 つの要素を結合するとき、ルートノードの集合の深さを比較する必要があります。プロセス全体の計算量は O(h) で、h は木の高さです。

...
public void unionElements(int p, int q){
    int pRoot = find(p);
    int qRoot = find(q);
    if( pRoot == qRoot )
        return;

    if( rank[pRoot] < rank[qRoot] ){
        parent[pRoot] = qRoot;
    }
    else if( rank[qRoot] < rank[pRoot]){
        parent[qRoot] = pRoot;
    }
    else{ // rank[pRoot] == rank[qRoot]
        parent[pRoot] = qRoot;
        rank[qRoot] += 1;   // このとき、rankの値を維持します
    }
}
...

Java 実例コード

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

UnionFind3.java ファイルのコード：

package サンプル.union;
/**
* rankに基づく最適化
 */
public class UnionFind4 {
    private int[] rank;   // rank[i]は、iをルートとする集合が表す木の深さを示します
    private int[] parent; // parent[i]は、i番目の要素が指す親ノードを示します
    private int count;    // データ数
    // コンストラクタ
    public UnionFind4(int count){
        rank = new int[count];
        parent = new int[count];
        this.count = count;
        // 初期化。各parent[i]は自分自身を指し、各要素が自分自身でひとつの集合を形成することを示します
        for( int i = 0 ; i < count ; i ++ ){
            parent[i] = i;
            rank[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;
        if( rank[pRoot] < rank[qRoot] ){
            parent[pRoot] = qRoot;
        }
        else if( rank[qRoot] < rank[pRoot]){
            parent[qRoot] = pRoot;
        }
        else{ // rank[pRoot] == rank[qRoot]
            parent[pRoot] = qRoot;
            rank[qRoot] += 1;   // rankの値を維持します
        }
    }
}
その他の拡張