素集合データ構造

ウィキペディア

素集合データ構造

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2026/11/02 23:38 UTC 版)

素集合データ構造
種類	多分木
発表時期	1964年
発明者	バーナード・ガラー、マイケル・フィッシャー
ビッグオー記法による計算量 (en)
アルゴリズム 平均 最悪の場合 空間 ${\\displaystyle O(n)}$ 6要素 a〜f での操作例。union(a, b)、union(c, d)、union(a, c) で木が連結され、find(d) の経路圧縮で d が根 a の直下に付け替えられる。続く union(b, e) では e が根 a の子になる。 表現 素集合森では、各集合の代表は木構造の根となる。各ノードは親ノードへのポインタを1つだけ持つ。根は自分自身を親として指すことで区別するのが一般的である（null ポインタなどの番兵を使う方法もある）。2つのノードが同じ集合に属する必要十分条件は、両者が属する木の根が同じことである。 アルゴリズムによっては、根のノードに木のサイズ（要素数）かランク（後述）のいずれかを補助情報として持たせる。これらは根でのみ必要なので、親ポインタを格納する領域にタグ付きポインタとして同居させることもできる。また、ノードを配列に格納して親を添字で表す実装もよく使われる。このとき親ポインタ1つあたり log2 n ビットが必要なので、森全体では Θ(n log n) ビットを要する。 MakeSet MakeSet は、新しい要素 x の親を x 自身にして、1要素だけの木を作る。サイズやランクを使う場合は同時に初期化する。1回の MakeSet は定数時間であり、n 個の要素で森を初期化するには O(n) の時間がかかる。 function MakeSet(x) x.parent := x x.size := 1 // サイズを使う場合 x.rank := 0 // ランクを使う場合 Find Find は親ノードへのリンクを根に到達するまでたどり、その根を返す。Union は2つの木を1つにする操作であり、どちらかの根が全体の根となる。以下に素朴な素集合森の実装例を擬似コードで示す。 function MakeSet(x) x.parent := x function Find(x) if x.parent == x return x else return Find(x.parent) function Union(x, y) xRoot := Find(x) yRoot := Find(y) xRoot.parent := yRoot この素朴な実装では、連結リストを使った場合と変わらない。なぜなら、木構造の平衡が保たれないからである。例えば要素 1, 2, …, n に対して Union(1, 2), Union(2, 3), …, Union(n−1, n) をこの順に実行すると、根が n で、1 から n までの経路が全ノードを通る1本の鎖ができ、Find(1) に O(n) かかる。しかし、これを改善する方法が2つある。 経路圧縮 経路圧縮の例。Find(a) の際に辿ったノード a, b, c の親が、すべて根 d に付け替えられる。 path compression（経路圧縮）は、Find操作を行ったときに構造を平坦化する改善である。Findで根ノードまでのリンクをたどっているとき、各ノードは同じ代表を共有しているので、それらを根ノードに直接接続できる。このため、Find は再帰的にたどったノードが全て親ノードとして根ノードを指すように変更する。こうすると木構造はより平坦になり、その後の操作が高速化される。この更新は集合の分割内容を変えないので、安全に行える。以下に Find の改良版を示す。 function Find(x) if x.parent == x return x else x.parent := Find(x.parent) return x.parent この再帰による実装は、根まで上る処理と根から戻る処理の2回の走査を行い、根までの経路を記憶する領域（上の擬似コードではコールスタック）を必要とする。根を探す走査と親を付け替える走査を同じ向きに2回行えば、記憶領域を定数にできる。 function Find(x) root := x while root.parent != root root := root.parent while x.parent != root parent := x.parent x.parent := root x := parent return root 経路分割と経路半減 Tarjan と van Leeuwen は、最悪計算量を保ったまま、根に向かう1回の走査だけで済み実用上より効率的な Find のアルゴリズムも考案している。これは経路分割（path splitting）と経路半減（path halving）と呼ばれ、どちらも経路上のノードの親を根に近いノードに付け替える。 経路分割は、経路上のすべてのノードの親を、そのノードの祖父（親の親）に付け替える。 function Find(x) while x.parent != x (x, x.parent) := (x.parent, x.parent.parent) return x 経路半減は、経路上の1つおきのノードだけの親を祖父に付け替える。 function Find(x) while x.parent != x x.parent := x.parent.parent x := x.parent return x 経路分割・経路半減は、再帰や経路の記憶を必要とせず、ループ1回で書けるため実装が簡潔である。 Union MakeSet により8個のシングルトンを作った状態。 いくつかの Union を行った後の状態。いくつかの集合が1つにまとまっている。 Union(x, y) は、まず Find で x と y それぞれの根を求める。根が同じなら何もしない。異なれば、一方の根の親をもう一方の根にして2つの木を連結する。どちらを親にするかは以降の操作の計算量に影響し、無頓着に選ぶと木が高くなりすぎる。木の高さを抑えるため、効率的な実装では union by size か union by rank を用いる。どちらも、根に親ポインタ以外の情報を持たせて、どちらの根を新しい親にするかを決める。 サイズによる併合 union by size（サイズによる併合）では、根が部分木の要素数（自分自身を含む子孫の数）を持ち、Union で要素数が大きい方の木の根を全体の根にする。要素数が等しければどちらでもよい。併合後の根のサイズは、2つのサイズの和に更新する。 function Union(x, y) xRoot := Find(x) yRoot := Find(y) if xRoot == yRoot return // x と y は既に同じ集合に属している // xRoot の方が要素数が大きくなるようにする if xRoot.size < yRoot.size (xRoot, yRoot) := (yRoot, xRoot) yRoot.parent := xRoot xRoot.size := xRoot.size + yRoot.size この方法では、要素が属する木の根までの深さは併合のたびに増えても、そのたびに属する木の要素数が2倍以上になるため、高さが log2 n を超えない。 ランクによる併合 union by rank（ランクによる併合）は、Union操作で常に大きい木の方が全体の根になるように連結するものである。木の大きさを評価するにはrank を用いる。これは、1要素の木の rank を 0 とし、同じ rank r の木を連結したとき、全体の根とした方の木の rank を r+1 とするものである。rank は木の高さの上限であるが、高さそのものではない。高さは Find の経路圧縮によって変化するので、高さを正確に保つ代わりに、rank を保持して更新の手間を避けている。このようにするだけで、MakeSet、Union、Find 操作の償却実行時間は ${\\displaystyle O(\\log n)}$ クラスカル法で最小全域木を求める際の Union-Find の動作例。 素集合データ構造は集合の分割をモデル化したもので、例えば無向グラフの連結成分などに対応する。したがって、2つの頂点が同じ成分に属するかどうかを調べたり、新たな辺を追加することで閉道となるかを調べるのに利用できる。辺を1本ずつ追加しながら、辺の両端が既に同じ集合に属していれば閉路ができたと判定できる。 Boost Graph Library では、Incremental Connected Components 機能の実装に素集合データ構造を使っている。また、グラフの最小全域木を求めるクラスカル法の実装にもこれを使っている。クラスカル法では、辺を重みの小さい順に見ていき、その両端が異なる集合に属する場合に限り辺を採用して2つの集合を併合する。 その他の応用として、次のものが挙げられる。 単一化の高性能な実装に Union-Find が用いられる。 Hoshen–Kopelman法（格子状のデータの連結成分のラベル付け）は Union-Find を使う。 型推論アルゴリズムの実装にも利用できる。 グラフから辺を削除していくクエリは、クエリを逆順に見ると辺の追加に変わるので、オフラインであれば Union-Find で処理できる。 なお、素集合森の実装では削除ができない点に注意されたい。上述した2つの改良を施しても削除は容易ではないが、削除に対応したもっと複雑な手法が既に設計されている（「要素の削除」の節を参照）。 歴史 素集合森は1964年に Galler と Fischer によって考案され、考案されてからよく使われていたが、1973年にジョン・ホップクロフトとジェフリー・ウルマンが、操作毎の時間の上限が O(log* n) であることを証明した。log* は反復対数であり、これも増加の遅い関数である（ただし、アッカーマン関数の逆関数ほどではない）。その後、上限（そして限定的な下限）がアッカーマン関数の逆関数であることを証明したのはロバート・タージャンだった。1975年に Tarjan が O(m α(n)) の上限を初めて証明し、この上限が厳密であることも示した。1979年には、Galler-Fischer 木を含むポインタアルゴリズムの範囲での下界を示した。タージャンと van Leeuwen はより効率的なワンパスの Find のアルゴリズムも考案している。1989年、Fredman と Saks が、任意の素集合データ構造に対して Ω(α(n)) の下界を示し、素集合森の最適性が一般の計算モデル（セルプローブモデル）でも確定した。 1991年には、Galil と Italiano が素集合データ構造に関する調査論文を発表した。同じ1991年には、Richard J. Anderson と Heather Woll が、ブロックすることなく並列化した Union-Find（wait-free な並列アルゴリズム）を発表している。 2007年、ACM SIGPLAN の Workshop on ML において、Sylvain Conchon と Jean-Christophe Filliâtre が素集合森データ構造の永続版を発表した。これは構造の以前のバージョンを効率的に保持するもので、計算機支援証明システムCoqを使って形式的に正しさが証明されている。最も高速な実装は、非永続のアルゴリズムとほぼ同等の性能を達成しているが、計算量の解析は行われていない。 関連項目 分割の精密化 - 集合を併合するのではなく、分割する方向で更新するデータ構造 動的連結性 クラスカル法 永続データ構造 外部リンク C++ disjoint sets implementation, part of the Boost C++ libraries Java implementation, part of JGraphT library Disjoint Sets の可視化, by David Galles Java applet: A Graphical Union-Find Implementation, by Rory L. P. McGuire