差分
このページの2つのバージョン間の差分を表示します。
次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming:algorithm:data_structure:union_find_tree [2017/08/07] – 作成 ikatakos | programming:algorithm:data_structure:union_find_tree [2017/08/07] – [実装] ikatakos | ||
---|---|---|---|
行 2: | 行 2: | ||
* 要素が$n$個ある | * 要素が$n$個ある | ||
- | * 各要素はグループに1つだけ属する | + | * 各要素は互いに素なグループに1つだけ属する |
- | * 「互いに素な集合」 | + | |
* 例: 生徒は必ず何かのクラブ活動に入り、かつ、兼部は認められていない | * 例: 生徒は必ず何かのクラブ活動に入り、かつ、兼部は認められていない | ||
* グループは統合される可能性がある。分割はされない | * グループは統合される可能性がある。分割はされない | ||
行 16: | 行 15: | ||
* [[https:// | * [[https:// | ||
* [[http:// | * [[http:// | ||
+ | * [[http:// | ||
=====アルゴリズム===== | =====アルゴリズム===== | ||
- | * 各グループの要素から、リーダーを1つ決める | + | * 各グループの要素から、" |
- | * リーダー以外の要素は、親となる要素を1つずつ持つ | + | * 代表以外の要素は、"親"となる要素を1つずつ持つ |
- | * つまり、1つのグループを、リーダーを根とした木構造で表現する | + | * どの要素からでも、親の親の親……を辿っていけば自身の代表に着くようにする |
- | * 親の親の親……を辿っていけばリーダーに着く | + | * つまり、グループを、代表を根とした木構造で表現する |
- | * ${\rm Union}(x, y)$は、yのリーダーの親をxのリーダーにする | + | < |
- | | + | |
+ | ↗↑ | ||
+ | 2 5 6 | ||
+ | | ||
+ | | ||
+ | </ | ||
- | =====高速化の工夫===== | + | * ${\rm Union}(x, y)$は、一方の代表を、もう一方の代表につなぐ(親にする) |
+ | * ${\rm Find}(x, y)$は、xとyから親を辿って同じ代表に行き着くか調べる | ||
- | | + | ====高速化の工夫==== |
- | * はやい例では、どの要素からも、1回調べたら親にたどり着ける | + | |
- | * おそい例では、4からだと、4→3→2→1と3回辿らないと親に着かない | + | |
+ | * 以下の例、はやい例では2~4のどの要素からも、1回調べたら代表にたどり着ける | ||
+ | * おそい例では、4からだと、4→3→2→1と3回辿らないと代表に着かない | ||
+ | * できるだけ、はやい例のような状態を保ちたい | ||
< | < | ||
◎はやい | ◎はやい | ||
行 43: | 行 52: | ||
</ | </ | ||
- | * 経路圧縮 | + | ===経路圧縮=== |
- | * 一度辿った経路上にある要素は、全て親をリーダーに書き換える | + | * 一度調べた経路上にある要素は、全て親を代表に書き換える |
- | * おそい例で4を調べて1がリーダーだとわかったら、3,4の親を1に書き換えておく(はやい例の状態にする) | + | * おそい例において、4→3→2→1と調べて1がリーダーだとわかったら、2~4の親を1に書き換える |
- | | + | |
- | * 木の深さ情報(ランク)を記録しておく | + | ===ランク=== |
- | * ${\rm Union}(a, b)$では、aとb、ランクの低い方の木を、高い方の木につなぐ | + | * 木の最大深さ(ランク)を記録しておく |
+ | * Union時、ランクの低い方のグループを、高い方のグループにつなぐ | ||
+ | * 互いのランクが等しい場合を除き、ランクが高くならずに済む(等しい場合のみ1増える) | ||
+ | |||
+ | < | ||
+ | この2つをUnionする場合| こうすると | ||
+ | | ||
+ | | ||
+ | | ||
+ | 2 3 4 | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | | ↑ | ||
+ | | | 8 | ||
+ | </ | ||
+ | |||
+ | ランクは深さでなく、要素数で考えることもある | ||
+ | |||
+ | * 例: 要素数100, | ||
+ | * 深さで考えるとBにAをつなぐことになる | ||
+ | * AにBをつなぐと最大深さが5になるとはいえ、影響ある要素は5個 | ||
+ | * それより、100個の要素の深さが1ずつ増える方が効率悪くない?という考え方 | ||
+ | * どちらがいいかは場合に依りけり? | ||
=====実装===== | =====実装===== | ||
+ | |||
+ | * 要素数$n$の配列'' | ||
+ | * ${\rm table}[x]$が負ならば、$x$は代表。絶対値はランクを示す | ||
+ | * ${\rm table}[x]$が非負ならば、$x$は代表でない。値は$x$の親を示す | ||
+ | * 最初は、$n$個の要素が別々の$n$個のグループに所属している状態 | ||
+ | * '' | ||
+ | * ついでに経路圧縮を行う | ||
<sxh python> | <sxh python> |