Union-Find クイックユニオン

一組のデータに対して、Union-Find は主に2つの操作をサポートします。

  • union(p,q) - p と q の2つの要素を接続します。

  • find(p)- p 要素がどの集合にあるかを検索します。

  • isConnected(p,q)- p と q の2つの要素が接続されているかどうかを確認します。

前のセクションでは、id配列の形式で Union-Find を表現しました。実際の操作における検索の時間計算量はO(1)、しかし接続の効率は高くありません。

このセクションでは、別の方法で Union-Find を実装します。各要素を1つのノードと見なし、自分の親ノードを指すようにします。ルートノードは自分自身を指します。下図のように、ノード3はノード2を指しています。これは3と2が接続されていることを表します。ノード2自体がルートノードなので、自分自身を指します。

同じく配列で Union-Find を表現しますが、次の一組の要素はparent現在の要素が指す親ノードを表します。各要素は自分自身を指し、すべて独立しています。

ここで、以下の操作を行うとunion(4,3)、要素4を要素3に向けます：

配列もそれに応じて変更されます：

2つの要素が接続されているかどうかを判断するには、ルートノードが同じかどうかを判断するだけです。

下図のように、ノード4とノード9のルートノードはどちらも8なので、それらは接続されています。

2つの要素を接続するには、それらの対応するルートノードを見つけ、ルートノードを接続するだけで、それらは接続されたノードになります。

上の図の6と4を接続したい場合は、6のルートノード5を4のルートノード8に向けるだけで済みます。

このような親ノードを指す木構造を構築するには、配列を使用して親ノードを指す木を構築します。parent[i] は i 要素が指す親ノードを表します。

...
private int[] parent;
private int count;  // データ数
...

検索プロセス：要素 p に対応する集合番号を検索します。自分の親ノードをルートノードに到達するまで繰り返し調べます。ルートノードの特徴は parent[p] == p です。計算量は O(h) で、h は木の高さです。

...
private int find(int p){
    assert( p >= 0 && p < count );
    while( p != parent[p] )
        p = parent[p];
    return p;
}
...

要素 p と要素 q が属する集合を結合します。それぞれの要素のルートノードを検索し、一方のルートノードをもう一方のルートノードに向けさせると、2つの集合が結合されます。この操作の時間計算量は O(h) で、h は木の高さです。

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

Java サンプルコード

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

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

package サンプル.union;
/**
* 第二版 UnionFind
 */
public class UnionFind2 {
    // 私たちの第二版 Union-Find。配列を使用して親ノードを指す木を構築する
    // parent[i] は i 番目の要素が指す親ノードを表す
    private int[] parent;
    private int count;  // データ数
    // コンストラクタ
    public UnionFind2(int count){
        parent = new int[count];
        this.count = count;
        // 初期化。各 parent[i] は自分自身を指し、各要素が自分自身で一つの集合を形成することを表す
        for( int i = 0 ; i < count ; i ++ )
            parent[i] = i;
    }
    // 検索プロセス。要素 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;
        parent[pRoot] = qRoot;
    }
}
その他の拡張