目次
文書の過去の版を表示しています。
Union-Find木
- 要素が $n$ 個あり、各要素は互いに素なグループに1つだけ属する
- 例: 生徒は必ず何かのクラブ活動に入り、兼部は認められていない
- グループは統合される可能性があるが、分割はされない
という前提で、
- ${\rm Union}(x, y)$: 要素xの属するグループと、yの属するグループを統合する
- ${\rm Find}(x, y)$: 要素xとyが同じグループに属するか調べる
という2つのクエリを効率的に処理するのが、Union-Find木
アルゴリズム
- 各グループの要素から、“代表”を1つ決める
- 代表以外の要素は、“親”となる要素を1つずつ持つ
- どの要素からでも、親の親の親……を辿っていけば自身の代表に着くようにする
- つまり、グループを、代表を根とした木構造で表現する
１ ４ ８ ←代表 ↗↑ ↑ ２ ５ ６ ↑ ↗ ↖ ３ ７ ９
- ${\rm Union}(x, y)$は、一方の代表を、もう一方の代表につなぐ（親にする）
- ${\rm Find}(x, y)$は、xとyから親を辿って同じ代表に行き着くか調べる
高速化の工夫
- 木の階層を低く保たないと、代表を見つける処理に時間がかかる
- 以下の例、はやい例では２～４のどの要素からも、1回調べたら代表にたどり着ける
- おそい例では、４からだと、４→３→２→１と3回辿らないと代表に着かない
- できるだけ、はやい例のような状態を保ちたい
◎はやい ×おそい
１ １
↗↑↖ ↑
２ ３ ４ ２
↑
３
↑
４
経路圧縮
- 一度調べた経路上にある要素は、全て親を代表に書き換える
- おそい例において、４→３→２→１と調べて１が代表だとわかったら、２～４の親を１に書き換える
ランク
- 木の最大深さ（ランク）を記録しておく
- Union時、ランクの低い方のグループを、高い方のグループにつなぐ
- 互いのランクが等しい場合を除き、ランクが高くならずに済む（等しい場合のみ1増える）
この2つをUnionする場合| こうすると | 低い方に高い方をつなげると
Rank:2 Rank:4 | Rank:4のまま | Rank:5になっちゃう
１ ５ | ５ | １
↗↑↖ ↑ | ↑↖ | ↗↗↑↖
２ ３ ４ ６ | １ ６ |２３ ４ ５
↑ | ↗↗↑ ↑ | ↑
７ | ２３ ４ ７ | ６
↑ | ↑ | ↑
８ | ８ | ７
| | ↑
| | ８
ランクは深さでなく、要素数で考えることもある
- 例: 要素数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で代表を再帰的に探索する- ついでに経路圧縮を行う
# Python3
class UnionFind:
def __init__(self, n):
# 負 : 根であることを示す。絶対値はランクを示す
# 非負: 根でないことを示す。値は親を示す
self.table = [-1] * n
def _root(self, x):
if self.table[x] < 0:
return x
else:
# 経路の圧縮
self.table[x] = self._root(self.table[x])
return self.table[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):
if self.table[x] < 0:
return x
else:
self.table[x] = self._root(self.table[x])
return self.table[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] = r1
