−目次
文書の過去の版を表示しています。
Union-Find木
- 要素が n 個あり、各要素は互いに素なグループに1つだけ属する
- 例: 生徒は必ず何かのクラブ活動に入り、兼部は認められていない
- グループは統合される可能性があるが、分割はされない
という前提で、
- Union(x,y): 要素xの属するグループと、yの属するグループを統合する
- Find(x,y): 要素xとyが同じグループに属するか調べる
という2つのクエリを効率的に処理するのが、Union-Find木
アルゴリズム
- 各グループの要素から、“代表”を1つ決める
- 代表以外の要素は、“親”となる要素を1つずつ持つ
- どの要素からでも、親の親の親……を辿っていけば自身の代表に着くようにする
- つまり、グループを、代表を根とした木構造で表現する
1 4 8 ←代表 ↗↑ ↑ 2 5 6 ↑ ↗ ↖ 3 7 9
- Union(x,y)は、一方の代表を、もう一方の代表につなぐ(親にする)
- 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で初期化する- table[x] が負ならば、x は代表。絶対値はランクを示す
- table[x] が非負ならば、x は代表でない。値は x の親を示す
- 最初は、n個の要素が別々のn個のグループに所属している状態
_root
で代表を再帰的に探索する- ついでに経路圧縮を行う
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
# 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の部分が少し変化。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
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 |