目次
文書の過去の版を表示しています。
Union-Find木
- 要素が $n$ 個あり、各要素は互いに素なグループに1つだけ属する
- 例: 生徒は必ず何かのクラブ活動に入り、兼部は認められていない
- グループは統合される可能性があるが、分割はされない
という前提で、
- ${\rm Unite}(x, y)$: 要素xの属するグループと、yの属するグループを統合する
- ${\rm Find}(x, y)$: 要素xとyが同じグループに属するか調べる
という2つのクエリを効率的に処理するのが、Union-Find木
アルゴリズム
- 各グループの要素から、“代表”を1つ決める
- 代表以外の要素は、“親”となる要素を1つずつ持つ
- どの要素からでも、親の親の親……を辿っていけば自身の代表に着くようにする
- つまり、グループを、代表を根とした木構造で表現する
1 4 8 ←1,4,8が代表 ↗↑ ↑ 2 5 6 ↑ ↗ ↖ 3 7 9
これをもとに、先ほどの2つの操作を言い換えると、以下のようになる。
- ${\rm Unite}(x, y)$は、一方の代表を、もう一方の代表につなぐ(親子にする)
- ${\rm Find}(x, y)$は、xとyから親を辿って同じ代表に行き着くか調べる
高速化の工夫
- 木の階層を低く保たないと、代表を見つける処理に時間がかかる
- 以下の例、はやい例では2~4のどの要素からも、1回調べたら代表にたどり着ける
- おそい例では、4からだと、4→3→2→1と3回辿らないと代表に着かない
- できるだけ、はやい例のような状態を保ちたい
◎はやい ×おそい 1 1 ↗↑↖ ↑ 2 3 4 2 ↑ 3 ↑ 4
経路圧縮
- 一度調べた経路上にある要素は、全て親を代表に書き換える
- おそい例において、一度UniteやFindクエリによって4→3→2→1と調べて1が代表だとわかったら、2~4の親を1に書き換える
ランク
- 木の最大深さ(ランク)を記録しておく
- Union時、ランクの低い方のグループを、高い方のグループにつなぐ
- 互いのランクが等しい場合を除き、ランクが高くならずに済む(等しい場合のみ1増える)
この2つをUnionする場合| こうすると | 低い方に高い方をつなげると Rank:2 Rank:4 | Rank:4のまま | Rank:5になっちゃう 1 5 | 5 | 1 ↗↑↖ ↑ | ↑↖ | ↗↗↑↖ 2 3 4 6 | 1 6 |23 4 5 ↑ | ↗↗↑ ↑ | ↑ 7 | 23 4 7 | 6 ↑ | ↑ | ↑ 8 | 8 | 7 | | ↑ | | 8
計算量
上記の2つの改善を行って、unite, find
1回にかかる計算量はいずれも $O(\alpha(N))$ となる(らしい)。
これはいずれもならし計算量で、何回もやると平均がこの値に近づいていく。
ただし $\alpha(N)$ はアッカーマン関数 $\rm{Ack}(N,N)$ の逆関数で、$N$ が少し大きくなると急速に小さくなるので、ほとんど定数と考えてよい。
実装
- 要素数 $n$ の配列
table
を作り、-1で初期化する- ${\rm table}[x]$ が負ならば、$x$ は代表。絶対値はランクを示す
- ${\rm table}[x]$ が非負ならば、$x$ は代表でない。値は $x$ の親を示す
- 最初は、$n$ 個の要素が別々の $n$ 個のグループに所属している状態
root
で代表を再帰的に探索する- ついでに経路圧縮を行う
2020/05 rootを非再帰に変更(特にPyPyで高速化)
unite()
のd1,d2は実際の値を正負逆転させているので、大小関係に注意。
# Python3 class UnionFind: def __init__(self, n): # 負 : 根であることを示す。絶対値はランクを示す # 非負: 根でないことを示す。値は親を示す self.table = [-1] * n def root(self, x): stack = [] tbl = self.table while tbl[x] >= 0: stack.append(x) x = tbl[x] for y in stack: tbl[y] = x return x def find(self, x, y): return self.root(x) == self.root(y) def unite(self, x, y): r1 = self.root(x) r2 = self.root(y) if r1 == r2: return # ランクの取得 d1 = self.table[r1] d2 = self.table[r2] if d1 <= d2: self.table[r2] = r1 if d1 == d2: self.table[r1] -= 1 else: self.table[r1] = r2 if __name__ == '__main__': ins = UnionFind(4) ins.unite(0, 1) ins.unite(2, 3) print(ins.find(0, 3)) # False ins.unite(1, 2) print(ins.find(0, 3)) # True
亜種
ランクを要素数とする
ランクは木の深さでなく、要素数で考えることもある。
- 例: 要素数100,最大深さ2のグループAと、要素数5,最大深さ4のグループB
- AにBを繋ぐとBの5個の要素の深さが1ずつ増え、最大深さは5
- BにAを繋ぐとAの100個の要素の深さが1ずつ増え、最大深さは4
- 局所的に最大深さが深くなろうが、100個の要素の深さが1ずつ増える方が効率悪くない?という考え方か
- A.V.Aho, John E. Hopcroft, Jeffrey D. Ulman, 『データ構造とアルゴリズム』, 培風館, 1987
実際、どちらを選んでも速度は体感できるほど変わらない。
木の深さってあまり使い道が無いが、「$x$ が含まれるグループの要素数」は任意の時点で取得できると嬉しい場合はある。
よって、ランクは要素数としておいた方が、何かと便利かも知れない。
実装
unite()
の中身が少し変化する。また、get_size()
を追加。
グループの要素も保持
上記の例では、グループの要素数はわかっても、具体的に現時点でのグループにはどの要素があるのか、というのはわからない。
グループの要素も管理したい場合、tableとは別にもう1つグループを管理する配列も用意して、実際に統合していく。
unite()
部分のならし計算量は、$O(\alpha(N))$ から $O(\alpha(N) \log{N})$ になる。
- $x$ が含まれるグループの要素を得たいときは、配列で $x$ の根の位置を参照する
- いったん根じゃなくなった要素はもう参照されないので、更新しなくてよい
unite()
でグループを統合する際は、2つのグループの要素数を比較して、大きい方へ小さい方を統合する- こうするだけで何もしない場合と比較して統合にかかるならし計算量が $O(N^2)$ から $O(\log{N})$ へ落とされる