目次
文書の過去の版を表示しています。
Union-Find木
- 要素が $n$ 個あり、各要素は互いに素なグループに1つだけ属する
- 例: 生徒は必ず何かのクラブ活動に入り、兼部は認められていない
- グループは統合される可能性があるが、分割はされない
という前提で、
- ${\rm Union}(x, y)$: 要素xの属するグループと、yの属するグループを統合する
- ${\rm Find}(x, y)$: 要素xとyが同じグループに属するか調べる
という2つのクエリを効率的に処理するのが、Union-Find木
アルゴリズム
- 各グループの要素から、“代表”を1つ決める
- 代表以外の要素は、“親”となる要素を1つずつ持つ
- どの要素からでも、親の親の親……を辿っていけば自身の代表に着くようにする
- つまり、グループを、代表を根とした木構造で表現する
1 4 8 ←代表 ↗↑ ↑ 2 5 6 ↑ ↗ ↖ 3 7 9
- ${\rm Union}(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
経路圧縮
- 一度調べた経路上にある要素は、全て親を代表に書き換える
- おそい例において、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
ランクは深さでなく、要素数で考えることもある
- 例: 要素数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
実装
- 要素数 $n$ の配列
table
を作り、-1で初期化する- ${\rm table}[x]$ が負ならば、$x$ は代表。絶対値はランクを示す
- ${\rm table}[x]$ が非負ならば、$x$ は代表でない。値は $x$ の親を示す
- 最初は、$n$個の要素が別々の$n$個のグループに所属している状態
_root
で代表を再帰的に探索する- ついでに経路圧縮を行う
2020/05 _rootを非再帰に変更(特にPyPyで高速化)
# 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 union(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.union(0, 1) ins.union(2, 3) print(ins.find(0, 3)) # False ins.union(1, 2) print(ins.find(0, 3)) # True
統合時、どちらを根にするかの基準をグループの深さで無く「要素数」とした実装。unionの部分が少し変化。
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 union(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 self.table[r1] += d2 else: self.table[r1] = r2 self.table[r2] += d1