差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:data_structure:union_find_tree [2019/09/21] – [実装] ikatakos | programming_algorithm:data_structure:union_find_tree [2021/01/31] – ikatakos | ||
|---|---|---|---|
| 行 9: | 行 9: | ||
| という前提で、 | という前提で、 | ||
| - | * ${\rm Union}(x, y)$: 要素xの属するグループと、yの属するグループを統合する | + | * ${\rm Unite}(x, y)$: 要素xの属するグループと、yの属するグループを統合する |
| * ${\rm Find}(x, y)$: 要素xとyが同じグループに属するか調べる | * ${\rm Find}(x, y)$: 要素xとyが同じグループに属するか調べる | ||
| 行 26: | 行 26: | ||
| < | < | ||
| - | １ ４ ８ ←代表 | + | １ ４ ８ ←1,4,8が代表 |
| ↗↑ | ↗↑ | ||
| ２ ５ ６ | ２ ５ ６ | ||
| 行 33: | 行 33: | ||
| </ | </ | ||
| - | | + | これをもとに、先ほどの2つの操作を言い換えると、以下のようになる。 |
| + | |||
| + | | ||
| * ${\rm Find}(x, y)$は、xとyから親を辿って同じ代表に行き着くか調べる | * ${\rm Find}(x, y)$は、xとyから親を辿って同じ代表に行き着くか調べる | ||
| 行 42: | 行 44: | ||
| * おそい例では、４からだと、４→３→２→１と3回辿らないと代表に着かない | * おそい例では、４からだと、４→３→２→１と3回辿らないと代表に着かない | ||
| * できるだけ、はやい例のような状態を保ちたい | * できるだけ、はやい例のような状態を保ちたい | ||
| + | |||
| < | < | ||
| ◎はやい | ◎はやい | ||
| 行 55: | 行 58: | ||
| ===経路圧縮=== | ===経路圧縮=== | ||
| * 一度調べた経路上にある要素は、全て親を代表に書き換える | * 一度調べた経路上にある要素は、全て親を代表に書き換える | ||
| - | * おそい例において、４→３→２→１と調べて１が代表だとわかったら、２～４の親を１に書き換える | + | * おそい例において、一度UniteやFindクエリによって４→３→２→１と調べて１が代表だとわかったら、２～４の親を１に書き換える |
| ===ランク=== | ===ランク=== | ||
| 行 75: | 行 78: | ||
| | | ８ | | | ８ | ||
| </ | </ | ||
| - | |||
| - | ランクは深さでなく、要素数で考えることもある | ||
| - | |||
| - | * 例: 要素数100, | ||
| - | * AにBを繋ぐとBの5個の要素の深さが1ずつ増え、最大深さは5 | ||
| - | * BにAを繋ぐとAの100個の要素の深さが1ずつ増え、最大深さは4 | ||
| - | * 局所的に最大深さが深くなろうが、100個の要素の深さが1ずつ増える方が効率悪くない？という考え方か | ||
| - | * A.V.Aho, John E. Hopcroft, Jeffrey D. Ulman, 『データ構造とアルゴリズム』, | ||
| =====実装===== | =====実装===== | ||
| 行 92: | 行 87: | ||
| * '' | * '' | ||
| * ついでに経路圧縮を行う | * ついでに経路圧縮を行う | ||
| + | |||
| + | < | ||
| <sxh python> | <sxh python> | ||
| 行 103: | 行 100: | ||
| def _root(self, x): | def _root(self, x): | ||
| - | | + | |
| - | | + | tbl = self.table |
| - | | + | while tbl[x] >= 0: |
| - | | + | |
| - | self.table[x] = self._root(self.table[x]) | + | x = tbl[x] |
| - | return | + | |
| + | | ||
| + | return x | ||
| def find(self, x, y): | def find(self, x, y): | ||
| 行 139: | 行 138: | ||
| </ | </ | ||
| - | 統合時、どちらを根にするかの基準をグループの深さで無く「要素数」とした実装。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, 『データ構造とアルゴリズム』, | ||
| + | |||
| + | 実際、どちらを選んでも速度は体感できるほど変わらない。 | ||
| + | |||
| + | 木の深さってあまり使い道が無いが、「$x$ が含まれるグループの要素数」は任意の時点で取得できると嬉しい場合はある。\\ | ||
| + | よって、ランクは要素数としておいた方が、何かと便利かも知れない。 | ||
| + | |||
| + | === 実装 | ||
| + | |||
| + | '' | ||
| + | |||
| + | '' | ||
| + | |||
| + | ++++ Python3 | | ||
| <sxh python> | <sxh python> | ||
| 行 147: | 行 169: | ||
| self.table = [-1] * n | self.table = [-1] * n | ||
| - | def _root(self, x): | + | def root(self, x): |
| - | | + | |
| - | return x | + | tbl = self.table |
| + | while tbl[x] >= 0: | ||
| + | | ||
| + | x = tbl[x] | ||
| + | for y in stack: | ||
| + | tbl[y] = x | ||
| + | | ||
| + | |||
| + | def find(self, x, y): | ||
| + | return self.root(x) == self.root(y) | ||
| + | |||
| + | def unite(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: | else: | ||
| - | self.table[x] = self._root(self.table[x]) | + | self.table[r1] = r2 |
| - | | + | |
| + | |||
| + | def get_size(self, x): | ||
| + | return -self.table[self.root(x)] | ||
| + | </ | ||
| + | |||
| + | ++++ | ||
| + | |||
| + | |||
| + | ==== グループの要素も保持 ==== | ||
| + | |||
| + | 上記の例では、グループの要素数はわかっても、具体的に現時点でのグループにはどの要素があるのか、というのはわからない。 | ||
| + | |||
| + | グループの要素も管理したい場合、tableとは別にもう1つグループを管理する配列も用意して、実際に統合していく。\\ | ||
| + | '' | ||
| + | |||
| + | * $x$ が含まれるグループの要素を得たいときは、配列で $x$ の根の位置を参照する | ||
| + | * いったん根じゃなくなった要素はもう参照されないので、更新しなくてよい | ||
| + | * '' | ||
| + | * こうするだけで何もしない場合と比較して統合にかかるならし計算量が $O(N^2)$ から $O(\log{N})$ へ落とされる | ||
| + | * [[http:// | ||
| + | |||
| + | ++++ Python3 | | ||
| + | |||
| + | <sxh python> | ||
| + | class UnionFindWithGrouping: | ||
| + | def __init__(self, | ||
| + | | ||
| + | self.group = [{i} for i in range(n)] | ||
| + | |||
| + | def root(self, | ||
| + | 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): | def find(self, x, y): | ||
| - | return self._root(x) == self._root(y) | + | return self.root(x) == self.root(y) |
| - | def union(self, x, y): | + | def unite(self, x, y): |
| - | r1 = self._root(x) | + | r1 = self.root(x) |
| - | r2 = self._root(y) | + | r2 = self.root(y) |
| if r1 == r2: | if r1 == r2: | ||
| return | return | ||
| + | |||
| d1 = self.table[r1] | d1 = self.table[r1] | ||
| d2 = self.table[r2] | d2 = self.table[r2] | ||
| 行 167: | 行 248: | ||
| self.table[r2] = r1 | self.table[r2] = r1 | ||
| self.table[r1] += d2 | self.table[r1] += d2 | ||
| + | self.group[r1].update(self.group[r2]) | ||
| else: | else: | ||
| self.table[r1] = r2 | self.table[r1] = r2 | ||
| self.table[r2] += d1 | self.table[r2] += d1 | ||
| + | self.group[r2].update(self.group[r1]) | ||
| + | |||
| + | def get_size(self, | ||
| + | return -self.table[self.root(x)] | ||
| + | |||
| + | def get_group(self, | ||
| + | return self.group[self.root(x)] | ||
| </ | </ | ||
| + | |||
| + | ++++ | ||
| + | |||
| + | |||
| + | |||
