Union-Find クイックファインド
この小節では、前の小節のUnion-Find構造に基づいて、基本操作である検索、結合、接続されているかどうかの判定を紹介します。
要素が属する集合の番号を検索し、直接返します。id配列の値、O(1)の時間計算量。
...
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
...
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;
}
...
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;
}
}
/**
* 第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;
}
}