差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming:algorithm:data_structure:union_find_tree [2017/08/07] – ikatakos | programming_algorithm:data_structure:union_find_tree [2019/08/25] – ikatakos | ||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ======Union-Find木====== | ======Union-Find木====== | ||
| - | * 要素が$n$個ある | + | |
| - | * 各要素はグループに1つだけ属する | + | |
| - | * 「互いに素な集合」 | + | |
| - | * 例: 生徒は必ず何かのクラブ活動に入り、かつ、兼部は認められていない | + | * 例: 生徒は必ず何かのクラブ活動に入り、兼部は認められていない |
| - | * グループは統合される可能性がある。分割はされない | + | * グループは統合される可能性があるが、分割はされない |
| という前提で、 | という前提で、 | ||
| 行 16: | 行 16: | ||
| * [[https:// | * [[https:// | ||
| * [[http:// | * [[http:// | ||
| + | * [[http:// | ||
| =====アルゴリズム===== | =====アルゴリズム===== | ||
| - | * 各グループの要素から、リーダーを1つ決める | + | * 各グループの要素から、" |
| - | * リーダー以外の要素は、親となる要素を1つずつ持つ | + | * 代表以外の要素は、"親"となる要素を1つずつ持つ |
| - | * つまり、1つのグループを、リーダーを根とした木構造で表現する | + | * どの要素からでも、親の親の親……を辿っていけば自身の代表に着くようにする |
| - | * 親の親の親……を辿っていけばリーダーに着く | + | * つまり、グループを、代表を根とした木構造で表現する |
| - | | + | < |
| - | * ${\rm Find}(x, y)$は、xとyから親を辿って同じリーダーに行き着くか調べる | + | １ ４ ８ ←代表 |
| + | ↗↑ | ||
| + | ２ ５ ６ | ||
| + | | ||
| + | | ||
| + | </ | ||
| + | |||
| + | | ||
| + | * ${\rm Find}(x, y)$は、xとyから親を辿って同じ代表に行き着くか調べる | ||
| - | =====高速化の工夫===== | + | ====高速化の工夫==== |
| - | * 木の階層を低く保たないと、リーダーを見つける処理に時間がかかる | + | * 木の階層を低く保たないと、代表を見つける処理に時間がかかる |
| - | * はやい例では、どの要素からも、1回調べたら親にたどり着ける | + | * 以下の例、はやい例では２～４のどの要素からも、1回調べたら代表にたどり着ける |
| - | * おそい例では、４からだと、４→３→２→１と3回辿らないと親に着かない | + | * おそい例では、４からだと、４→３→２→１と3回辿らないと代表に着かない |
| + | * できるだけ、はやい例のような状態を保ちたい | ||
| < | < | ||
| ◎はやい | ◎はやい | ||
| 行 43: | 行 53: | ||
| </ | </ | ||
| - | * 経路圧縮 | + | ===経路圧縮=== |
| - | * 一度調べた経路上にある要素は、全て親をリーダーに書き換える | + | * 一度調べた経路上にある要素は、全て親を代表に書き換える |
| - | * おそい例において、４を調べて１がリーダーだとわかったら、３,４の親を１に書き換える | + | * おそい例において、４→３→２→１と調べて１が代表だとわかったら、２～４の親を１に書き換える |
| - | | + | |
| - | * 木の深さ情報（ランク）を記録しておく | + | ===ランク=== |
| - | * Unionでは、ランクの低い方のグループを、高い方のグループに吸収させる | + | * 木の最大深さ（ランク）を記録しておく |
| + | * Union時、ランクの低い方のグループを、高い方のグループにつなぐ | ||
| + | * 互いのランクが等しい場合を除き、ランクが高くならずに済む（等しい場合のみ1増える） | ||
| + | |||
| + | < | ||
| + | この2つをUnionする場合| こうすると | ||
| + | | ||
| + | | ||
| + | | ||
| + | ２ ３ ４ | ||
| + | | ||
| + | | ||
| + | | ||
| + | | ||
| + | | | ↑ | ||
| + | | | ８ | ||
| + | </ | ||
| + | |||
| + | ランクは深さでなく、要素数で考えることもある | ||
| + | |||
| + | * 例: 要素数100, | ||
| + | * AにBを繋ぐとBの5個の要素の深さが1ずつ増え、最大深さは5 | ||
| + | * BにAを繋ぐとAの100個の要素の深さが1ずつ増え、最大深さは4 | ||
| + | * 局所的に最大深さが深くなろうが、100個の要素の深さが1ずつ増える方が効率悪くない？という考え方か | ||
| + | * A.V.Aho, John E. Hopcroft, Jeffrey D. Ulman, 『データ構造とアルゴリズム』, | ||
| =====実装===== | =====実装===== | ||
| + | |||
| + | * 要素数 $n$ の配列'' | ||
| + | * ${\rm table}[x]$ が負ならば、$x$ は代表。絶対値はランクを示す | ||
| + | * ${\rm table}[x]$ が非負ならば、$x$ は代表でない。値は $x$ の親を示す | ||
| + | * 最初は、$n$個の要素が別々の$n$個のグループに所属している状態 | ||
| + | * '' | ||
| + | * ついでに経路圧縮を行う | ||
| <sxh python> | <sxh python> | ||
| 行 96: | 行 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] = r1 | ||
| </ | </ | ||
