素集合データ構造 (Union-Find木)
問題
次の問題について考えます.
[問題] ある集合が, 互いに素な部分集合の族によって完全に分類されているとする. このとき, 与えられた二つの元が, 同一の部分集合に属するかどうか判定せよ.
もう少し丁寧に説明すると, ある集合 $S$ が与えられたとして, その部分集合の族 $F_i \subset S$ ($i = 0, 1, 2, ...$) が次の条件を満たすとします. $$i \neq j \ \ \Rightarrow \ \ F_i \cap F_j = \emptyset$$ $$\bigcup_i F_i = S$$ このとき, $S$ のふたつの元 $a$, $b$ が与えられたとき, それが同一の $F_i$ に属する元かどうか判定してください, という問題です.
この問題は, グラフ理論の言葉を用いると次のように述べることもできます.
[問題] 連結とは限らない無向グラフが与えられたとする. その二つの頂点が与えられたとき, それらを結ぶ道が存在するかどうか判定せよ. ただし, すべての頂点は自分自身と自明な道で結ばれているものと解釈する.
つまり, 与えられたふたつの頂点が同一の連結成分上のものかどうか判定せよ, ということですね. 与えられたグラフの各連結成分が, 上の問題でいう部分集合 $F_i$ に相当します. 以下ではこのグラフ理論の言葉づかいを用いて議論を進めます.
考え方
グラフの定義
与えられたグラフの頂点の数を $N$ とし, 各頂点を $0$ から $N - 1$ までの番号でラベル付けします. 無向グラフは, 辺 (頂点と頂点の組) をすべて与えることによって定義されます. 例えば, 次のグラフの定義では, 1行にふたつの数 $a$, $b$ が書かれていますが, これは頂点 $a$, $b$ を結ぶ辺が存在する, という意味です.
1 2
3 4
3 2
2 4
4 2
0 0
最終行では端点が同一の頂点であるような辺 (ループ) が定義されていますが, いまの問題では頂点は自分自身と道で結ばれていますから, その存在はまったく無意味です. また, 第4行と第5行では頂点 2, 4 を結ぶ二つの辺が定義されています (多重辺) が, いまの問題の範疇ではやはり多重辺は意味を持ちません. つまり, 仮に第5行と第6行を省略しても問題の答えは変わりません.
木構造による表現
この問題は, 実は (グラフ構造ではなく) 木構造を用いた方が簡単です. 頂点 $a$, $b$ を結ぶ辺が存在するということを, $a$ を親, $b$ を子とする木構造と解釈し直してみましょう (無向グラフを考えているため, どちらが親かは重要ではなく, 逆にしても構いません).
最初は辺が一切ない状態から出発します. このとき, すべての頂点は自分自身を根とする自明な木を構成しています.
[0] [1] [2] [3] [4]
ここに最初の辺 $(1, 2)$ を追加します. この操作は, 頂点 $2$ を頂点 $1$ の子とすることでふたつの木を結合する (union) ものとみなせます.
[0] [1] [3] [4]
│
[2]
第二の辺 $(3, 4)$ の追加も同様です.
[0] [1] [3]
│ │
[2] [4]
第三の辺 $(3, 2)$ ですが, 頂点 $2$ は根ではないので, それを頂点 $3$ の子とするのではなく, 頂点 $2$ の根である頂点 $1$ を頂点 $3$ の子とします.
[0] [3]
╱ ╲
[1] [4]
│
[2]
第四の辺 $(2, 4)$ ですが, 既に頂点 $2$, $4$ はひとつの木にまとめられていますから, 何もする必要はありません. ここでどうやって頂点 $2$, $4$ がひとつの木にまとまっているか判定したかというと, 木を辿ることで両者の根を調べ, それがどちらも頂点 $3$ で一致したため同じ木だと判断したのです. 残りの辺も同様に何も操作は要りません. 以上の木構造を構成する過程は Union と呼ばれています.
与えられたグラフを上述の木構造にまとめることができたら, 後は簡単です. 頂点 $a$, $b$ が連結かどうかは, $a$, $b$ の親を辿って行ったときに得られる根が一致するかどうか, によって判定できます. この過程は Find と呼ばれています.
最適化 (1) 経路圧縮
考え方は以上の通りなのですが, この操作を愚直に行っても速いとは言えません. ある頂点について, その親を求める操作に木の高さ分だけの時間を要するからです. しかし, いまの問題では木構造は重要ではなく, どの根と繋がっているかだけが重要です. そこで, ある頂点についてその根を求める操作をした際には, その頂点を根の直接の子となるように繋ぎ直してしまえばよいのです.
この繋ぎ直しは, 頂点から根まで辿る経路上の途中の頂点についても行うことができ, すべて根の子にしてしまいましょう. そうすれば次回以降その木の操作を行う際に動作が速くなります.
最適化 (2) union by rank
さらに, 上の説明ではふたつの木を結合する操作を, 単純に入力通りにしていました. しかし, ふたつの木の高さがわかっているならば, より高さの小さい方を子として結合することで, 木の高さが増大するのを抑えることができます.
Rust コード
もう少し最適化できると思いますが, 疲れたのでここまで.
#[derive(Debug)]
struct Node {
parent: Option<usize>,
}
#[derive(Debug)]
struct UFTree {
arena: Vec<Node>,
}
impl UFTree {
/// 与えられたノードの根を探索しそのインデックスを返す.
fn root(&mut self, vertex: usize) -> usize {
// 根まで木を辿る
let r = match self.arena[vertex].parent {
Some(p) => {
self.root(p)
},
None => vertex,
};
// 問題のノードを根に直接繋ぎ直す
if let Some(_) = self.arena[vertex].parent {
self.arena[vertex].parent = Some(r);
}
// 根のインデックスを返す
r
}
/// 与えられたノードの根を探索しそのインデックスを返す.
/// 同時に, 根まで辿るのに要した階層の数 (rank) を計算する.
fn root_with_rank(&mut self, vertex: usize) -> (usize, usize) {
// 根まで木を辿る
let (r, level) = match self.arena[vertex].parent {
Some(p) => {
let (r, level) = self.root_with_rank(p);
(r, level + 1)
},
None => (vertex, 0),
};
// 問題のノードを根に直接繋ぎ直す
if let Some(_) = self.arena[vertex].parent {
self.arena[vertex].parent = Some(r);
}
// 根のインデックスを返す
(r, level)
}
/// ふたつのノードを含む部分木をひとつにまとめる.
fn unite(&mut self, a: usize, b: usize) {
let (root_of_a, rank_of_a) = self.root_with_rank(a);
let (root_of_b, rank_of_b) = self.root_with_rank(b);
if root_of_a != root_of_b {
if rank_of_a > rank_of_b {
self.arena[root_of_b].parent = Some(root_of_a);
} else {
self.arena[root_of_a].parent = Some(root_of_b);
}
}
}
/// ふたつのノードが同一の部分木に属するか判定する.
fn find(&mut self, a: usize, b: usize) -> bool {
self.root(a) == self.root(b)
}
}