差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming:algorithm:data_structure:union_find_tree [2017/08/07] – ikatakos | programming_algorithm:data_structure:union_find_tree [2019/09/21] – [実装] ikatakos | ||
---|---|---|---|
行 1: | 行 1: | ||
======Union-Find木====== | ======Union-Find木====== | ||
- | * 要素が$n$個ある | + | |
- | * 各要素は互いに素なグループに1つだけ属する | + | |
- | * 例: 生徒は必ず何かのクラブ活動に入り、かつ、兼部は認められていない | + | |
- | * グループは統合される可能性がある。分割はされない | + | * 例: 生徒は必ず何かのクラブ活動に入り、兼部は認められていない |
+ | * グループは統合される可能性があるが、分割はされない | ||
という前提で、 | という前提で、 | ||
行 54: | 行 55: | ||
===経路圧縮=== | ===経路圧縮=== | ||
* 一度調べた経路上にある要素は、全て親を代表に書き換える | * 一度調べた経路上にある要素は、全て親を代表に書き換える | ||
- | * おそい例において、4→3→2→1と調べて1がリーダーだとわかったら、2~4の親を1に書き換える | + | * おそい例において、4→3→2→1と調べて1が代表だとわかったら、2~4の親を1に書き換える |
===ランク=== | ===ランク=== | ||
行 78: | 行 79: | ||
* 例: 要素数100, | * 例: 要素数100, | ||
- | * 深さで考えるとBにAをつなぐことになる | + | * AにBを繋ぐとBの5個の要素の深さが1ずつ増え、最大深さは5 |
- | * AにBをつなぐと最大深さが5になるとはいえ、影響ある要素は5個 | + | * BにAを繋ぐとAの100個の要素の深さが1ずつ増え、最大深さは4 |
- | * それより、100個の要素の深さが1ずつ増える方が効率悪くない?という考え方 | + | * 局所的に最大深さが深くなろうが、100個の要素の深さが1ずつ増える方が効率悪くない?という考え方か |
- | * どちらがいいかは場合に依りけり? | + | * A.V.Aho, John E. Hopcroft, Jeffrey D. Ulman, 『データ構造とアルゴリズム』, |
=====実装===== | =====実装===== | ||
- | * 要素数$n$の配列{\rm table}を作り、-1で初期化する | + | * 要素数 $n$ の配列'' |
- | * ${\rm table}[x]$が負ならば、$x$は代表。絶対値はランクを示す | + | * ${\rm table}[x]$ が負ならば、$x$ は代表。絶対値はランクを示す |
- | * ${\rm table}[x]$が非負ならば、$x$は代表でない。値は$x$の親を示す | + | * ${\rm table}[x]$ が非負ならば、$x$ は代表でない。値は $x$ の親を示す |
* 最初は、$n$個の要素が別々の$n$個のグループに所属している状態 | * 最初は、$n$個の要素が別々の$n$個のグループに所属している状態 | ||
* '' | * '' | ||
行 136: | 行 137: | ||
print(ins.find(0, | print(ins.find(0, | ||
+ | </ | ||
+ | |||
+ | 統合時、どちらを根にするかの基準をグループの深さで無く「要素数」とした実装。unionの部分が少し変化。 | ||
+ | |||
+ | <sxh python> | ||
+ | |||
+ | class UnionFind: | ||
+ | def __init__(self, | ||
+ | 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] += d1 | ||
</ | </ |