Union-Find クイックファインド

この小節では、前の小節のUnion-Find構造に基づいて、基本操作である検索、結合、接続されているかどうかの判定を紹介します。

要素が属する集合の番号を検索し、直接返します。id配列の値、O(1)の時間計算量。

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

要素を結合するpと要素q所属する集合。結合プロセスではすべての要素を一度走査し、2つの要素の所属集合番号を結合する必要があります。このプロセスはO(n)複雑度。

...
public void unionElements(int p, int q) {
    int pID = find(p);
    int qID = find(q);
    if (pID == qID)
        return;
    for (int i = 0; i < count; i++)
        if (id[i] == pID)
            id[i] = qID;
}
...

Java サンプルコード

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

UnionFind1.java ファイルのコード:

package サンプル.union;

/**
* 第1版union-Find
 */

public class UnionFind1 {
    // 私たちの第1版Union-Findは本質的に配列です
    private int[] id;
    // データの個数
    private int count;

    public UnionFind1(int n) {
        count = n;
        id = new int[n];
        // 初期化、各id[i]は自分自身を指し、結合された要素はありません
        for (int i = 0; i < n; i++)
            id[i] = i;
    }

    // 検索プロセス、要素pが対応する集合の番号を検索します
    private int find(int p) {
        assert p >= 0 && p < count;
        return id[p];
    }

    // 要素pと要素qが同じ集合に属するかどうかを確認します
    // O(1) 計算量
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    // 要素pと要素qが属する集合を結合します
    // O(n) 計算量
    public void unionElements(int p, int q) {

        int pID = find(p);
        int qID = find(q);

        if (pID == qID)
            return;

        // 結合プロセスではすべての要素を一度走査し、2つの要素の所属集合番号を結合する必要があります
        for (int i = 0; i < count; i++)
            if (id[i] == pID)
                id[i] = qID;
    }
}
その他の拡張