差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming:algorithm:data_structure:union_find_tree [2017/08/07] – ikatakos | programming_algorithm:data_structure:union_find_tree [2021/01/31] – [高速化の工夫] ikatakos | ||
---|---|---|---|
行 1: | 行 1: | ||
======Union-Find木====== | ======Union-Find木====== | ||
- | * 要素が$n$個ある | + | |
- | * 各要素はグループに1つだけ属する | + | |
- | * 「互いに素な集合」 | + | |
- | * 例: 生徒は必ず何かのクラブ活動に入り、かつ、兼部は認められていない | + | * 例: 生徒は必ず何かのクラブ活動に入り、兼部は認められていない |
- | * グループは統合される可能性がある。分割はされない | + | * グループは統合される可能性があるが、分割はされない |
という前提で、 | という前提で、 | ||
- | * ${\rm Union}(x, y)$: 要素xの属するグループと、yの属するグループを統合する | + | * ${\rm Unite}(x, y)$: 要素xの属するグループと、yの属するグループを統合する |
* ${\rm Find}(x, y)$: 要素xとyが同じグループに属するか調べる | * ${\rm Find}(x, y)$: 要素xとyが同じグループに属するか調べる | ||
行 16: | 行 16: | ||
* [[https:// | * [[https:// | ||
* [[http:// | * [[http:// | ||
+ | * [[http:// | ||
=====アルゴリズム===== | =====アルゴリズム===== | ||
- | * 各グループの要素から、リーダーを1つ決める | + | * 各グループの要素から、" |
- | * リーダー以外の要素は、親となる要素を1つずつ持つ | + | * 代表以外の要素は、"親"となる要素を1つずつ持つ |
- | * つまり、1つのグループを、リーダーを根とした木構造で表現する | + | * どの要素からでも、親の親の親……を辿っていけば自身の代表に着くようにする |
- | * 親の親の親……を辿っていけばリーダーに着く | + | * つまり、グループを、代表を根とした木構造で表現する |
- | | + | < |
- | * ${\rm Find}(x, y)$は、xとyから親を辿って同じリーダーに行き着くか調べる | + | 1 4 8 ←1, |
+ | ↗↑ | ||
+ | 2 5 6 | ||
+ | | ||
+ | | ||
+ | </ | ||
+ | |||
+ | これをもとに、先ほどの2つの操作を言い換えると、以下のようになる。 | ||
+ | |||
+ | | ||
+ | * ${\rm Find}(x, y)$は、xとyから親を辿って同じ代表に行き着くか調べる | ||
+ | |||
+ | ==== 高速化の工夫 ==== | ||
- | =====高速化の工夫===== | + | * 木の階層を低く保たないと、代表を見つける処理に時間がかかる |
+ | * 以下の例、はやい例では2~4のどの要素からも、1回調べたら代表にたどり着ける | ||
+ | * おそい例では、4からだと、4→3→2→1と3回辿らないと代表に着かない | ||
+ | * できるだけ、はやい例のような状態を保ちたい | ||
- | * 木の階層を低く保たないと、リーダーを見つける処理に時間がかかる | ||
- | * はやい例では、どの要素からも、1回調べたら親にたどり着ける | ||
- | * おそい例では、4からだと、4→3→2→1と3回辿らないと親に着かない | ||
< | < | ||
◎はやい | ◎はやい | ||
行 43: | 行 56: | ||
</ | </ | ||
- | * 経路圧縮 | + | ===経路圧縮=== |
- | * 一度調べた経路上にある要素は、全て親をリーダーに書き換える | + | * 一度調べた経路上にある要素は、全て親を代表に書き換える |
- | * おそい例において、4を調べて1がリーダーだとわかったら、3,4の親を1に書き換える | + | * おそい例において、一度UniteやFindクエリによって4→3→2→1と調べて1が代表だとわかったら、2~4の親を1に書き換える |
- | | + | |
- | * 木の深さ情報(ランク)を記録しておく | + | ===ランク=== |
- | * Unionでは、ランクの低い方のグループを、高い方のグループに吸収させる | + | * 木の最大深さ(ランク)を記録しておく |
+ | * Union時、ランクの低い方のグループを、高い方のグループにつなぐ | ||
+ | * 互いのランクが等しい場合を除き、ランクが高くならずに済む(等しい場合のみ1増える) | ||
+ | |||
+ | < | ||
+ | この2つをUnionする場合| こうすると | ||
+ | | ||
+ | | ||
+ | | ||
+ | 2 3 4 | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | | ↑ | ||
+ | | | 8 | ||
+ | </ | ||
+ | |||
+ | ==== 計算量 ==== | ||
+ | |||
+ | 上記の2つの改善を行って、'' | ||
+ | |||
+ | これはいずれもならし計算量で、何回もやると平均がこの値に近づいていく。 | ||
+ | |||
+ | ただし $\alpha(N)$ はアッカーマン関数 $\rm{Ack}(N, | ||
+ | |||
+ | * [[https:// | ||
+ | |||
+ | |||
=====実装===== | =====実装===== | ||
+ | |||
+ | * 要素数 $n$ の配列'' | ||
+ | * ${\rm table}[x]$ が負ならば、$x$ は代表。絶対値はランクを示す | ||
+ | * ${\rm table}[x]$ が非負ならば、$x$ は代表でない。値は $x$ の親を示す | ||
+ | * 最初は、$n$ 個の要素が別々の $n$ 個のグループに所属している状態 | ||
+ | * '' | ||
+ | * ついでに経路圧縮を行う | ||
+ | |||
+ | < | ||
<sxh python> | <sxh python> | ||
行 61: | 行 112: | ||
self.table = [-1] * n | self.table = [-1] * n | ||
- | 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): | ||
- | 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 | ||
行 90: | 行 143: | ||
if __name__ == ' | if __name__ == ' | ||
ins = UnionFind(4) | ins = UnionFind(4) | ||
- | ins.union(0, 1) | + | ins.unite(0, 1) |
- | ins.union(2, 3) | + | ins.unite(2, 3) |
print(ins.find(0, | print(ins.find(0, | ||
- | ins.union(1, 2) | + | ins.unite(1, 2) |
print(ins.find(0, | print(ins.find(0, | ||
</ | </ | ||
+ | |||
+ | ===== 亜種 ===== | ||
+ | |||
+ | ==== ランクをグループの要素数とする ==== | ||
+ | |||
+ | ランクは木の深さでなく、要素数で考えることもある。 | ||
+ | |||
+ | * 例: 要素数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> | ||
+ | |||
+ | class UnionFind: | ||
+ | def __init__(self, | ||
+ | self.table = [-1] * n | ||
+ | |||
+ | def root(self, x): | ||
+ | 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): | ||
+ | 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: | ||
+ | self.table[r1] = r2 | ||
+ | self.table[r2] += d1 | ||
+ | |||
+ | def get_size(self, | ||
+ | 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.table = [-1] * n | ||
+ | self.group = [{i} for i in range(n)] | ||
+ | |||
+ | def root(self, x): | ||
+ | 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): | ||
+ | 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 | ||
+ | self.group[r1].update(self.group[r2]) | ||
+ | else: | ||
+ | self.table[r1] = r2 | ||
+ | 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)] | ||
+ | </ | ||
+ | |||
+ | ++++ | ||
+ | |||
+ | |||
+ |