Union-Find の基本きほん

1導入どうにゅう

この講義こうぎでは、互たがいに素そな集合族しゅうごうぞくが定さだめる分割ぶんかつを定義ていぎし、find と union を提供ていきょうする Union-Find の表現ひょうげんおよび計算量けいさんりょうを説明せつめいする。

2素集合分割そしゅうごうぶんかつと操作そうさ

集合しゅうごう $$U$$U の分割ぶんかつpartitionとは、空くうでない部分集合族ぶぶんしゅうごうぞく $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P$$\mathcal P であって、異ことなる二集合にしゅうごうが互たがいに素そであり、その和集合わしゅうごうが $$U$$U となるものである。Union-Find（disjoint-set union）は、この分割ぶんかつに対たいして次つぎの操作そうさを提供ていきょうする。

• $$\mathrm{find}\left(x\right)$$\operatorname{find}(x) は、$$x$$x を含ふくむ集合しゅうごうに割わり当あてられた代表元だいひょうげんrepresentativeを返かえす。同一集合どういつしゅうごうの要素ようそは同一どういつの代表元だいひょうげんをもち、$$\mathrm{find}\left(x\right)=\mathrm{find}\left(y\right)$$\operatorname{find}(x)=\operatorname{find}(y) と $$x,y$$x,y が同一集合どういつしゅうごうに属ぞくすることは同値どうちである。
• $$\mathrm{union}(x,y)$$\operatorname{union}(x,y) は、$$x$$x と $$y$$y を含ふくむ二集合にしゅうごうを一集合いちしゅうごうへ併合へいごうする。既すでに同一集合どういつしゅうごうなら分割ぶんかつを変更へんこうしない。

初期状態しょきじょうたいでは、各要素かくようそが一要素集合いちようそしゅうごうを構成こうせいするものとする。Union-Find は集合しゅうごうの併合へいごうを処理しょりするが、集合しゅうごうの分割ぶんかつや要素ようその削除さくじょは標準操作ひょうじゅんそうさに含ふくまれない。

find と union の引数ひきすうは $$U$$U の要素ようそであることを事前条件じぜんじょうけんとする。$$U=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$U=\varnothing の場合ばあい、初期分割しょきぶんかつは空族くうぞくであり、有効ゆうこうな find または union の呼出よびだしは存在そんざいしない。

3親おやの森もりによる表現ひょうげん

各集合かくしゅうごうを根付ねつき木ぎで表現ひょうげんし、全体ぜんたいを根付ねつき木ぎの森もりとして保持ほじする。各要素かくようそ $$x$$x は親おや $$\mathrm{parent}\left[x\right]$$\operatorname{parent}[x] をもち、根ね $$r$$r では $$\mathrm{parent}\left[r\right]=r$$\operatorname{parent}[r]=r とする。根ねがその集合しゅうごうの代表元だいひょうげんである。find は親おやを反復的はんぷくてきに参照さんしょうして根ねへ到達とうたつし、union は二ふたつの根ねの一方いっぽうを他方たほうの子こにする。

3.1経路圧縮けいろあっしゅく

find の実行中じっこうちゅうに参照さんしょうした各頂点かくちょうてんの親おやを根ねへ変更へんこうする方法ほうほうを経路圧縮けいろあっしゅくpath compressionという。分割ぶんかつと代表元だいひょうげんを変更へんこうせず、後続こうぞくする find の親参照回数おやさんしょうかいすうを削減さくげんする。

3.2ランクによる併合へいごう

根ねに木きの高たかさの上界じょうかいを表あらわすランクrankを保持ほじし、union で小ちいさいランクの根ねを大おおきいランクの根ねの子こにする。同一どういつのランクなら一方いっぽうを子こにし、新あたらしい根ねのランクを $$1$$1 増加ぞうかさせる。経路圧縮後けいろあっしゅくごのランクは実際じっさいの高たかさと一致いっちするとは限かぎらないが、併合規則へいごうきそくに使用しようできる。

4計算量けいさんりょうと適用範囲てきようはんい

配列要素はいれつようその参照さんしょうと更新こうしんを $$O\left(1\right)$$O(1) とする計算模型けいさんもけいを仮定かていする。$$n$$n 個この一要素集合いちようそしゅうごうの初期化しょきかと、経路圧縮けいろあっしゅくおよびランクによる併合へいごうを併用へいようした $$m$$m 回かいの find・union からなる操作列そうされつの総時間そうじかんには、標準的ひょうじゅんてきな簡略上界かんりゃくじょうかい $$O\left(\right(n+m\left)\alpha \right(n\left)\right)$$O((n+m)\alpha(n)) を使用しようできる。ここで $$\alpha$$\alpha は逆ぎゃく Ackermann 関数かんすうである。より精密せいみつな表記ひょうきでは、その引数ひきすうを $$n$$n と $$m$$m の双方そうほうから定さだめる。この評価ひょうかは操作列全体そうされつぜんたいに対たいするならし計算量けいさんりょうamortized complexityであり、各操作かくそうさの最悪時間さいあくじかんが定数ていすうであることを意味いみしない。記憶領域きおくりょういきは $$O\left(n\right)$$O(n) である。

無向むこうグラフへ辺へんを追加ついかする際さいに両端点りょうたんてんを union すれば、find の代表元だいひょうげんの比較ひかくによって連結性れんけつせいを管理かんりできる。ただし、Union-Find は連結経路れんけつけいろや最短路さいたんろを復元ふくげんせず、辺へんの削除さくじょを直接ちょくせつには処理しょりしない。