素集合データ構造
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/10/07 05:02 UTC 版)
ナビゲーションに移動 検索に移動素集合データ構造（そしゅうごうデータこうぞう、英: disjoint-set data structure）は、データの集合を素集合（互いにオーバーラップしない集合）に分割して保持するデータ構造。このデータ構造に対する以下の2つの便利な操作をUnion-Findアルゴリズムと呼ぶ。
- Find: 特定の要素がどの集合に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。
- Union: 2つの集合を1つに統合する。
これら2つの操作をサポートしているため、素集合データ構造は「Union-Findデータ構造」あるいは「Merge-Find集合」とも呼ばれる。これら以外の重要な操作として MakeSetがある。これは、与えられた1つの要素だけを格納した集合（シングルトン）を作成する。これら3つの操作により、様々な実用的分割問題を解くことができる（「応用」の節を参照）。
これらの操作をより正確に定義するには、集合の表現方法を決める必要がある。典型的な手法としては、それぞれの集合について、ある固定の要素を選択して「代表 (representative)」とし、その集合全体を表すものとする。すると Find(x) は x が属する集合の代表を返す。また、Union は2つの代表を引数とする。
素集合連結リスト
素集合データ構造を生成する単純な手法としては、集合毎に連結リストを生成する方法がある。リストの先頭の要素がその集合の代表となる。
MakeSetは1要素のリストを生成する。Unionは2つのリストを連結する操作で、定数時間の操作である。この実装の欠点は、FindがΩ(n)または線形時間を必要とする点である。
これを防ぐには、連結リストの各ノードにそのリストの先頭へのポインタを格納しておけばよい。つまり、Findの引数がノードへのポインタであれば、即座にそのノードが属するリストの先頭（代表）がわかる。しかし、このように実装すると今度はUnion操作で各ノードの先頭へのポインタを更新しなければならなくなり、Ω(n) の時間がかかるようになる。
各リストの長さがわかっているなら、短い方を長い方に連結することでUnionの性能を改善できる。これ (weighted-union heuristic) を採用すると、n個の要素について、m回のMakeSet、Union、Find操作を行ったときにかかる時間は O(m + nlog n) となる[1]。漸近的により高速な操作には別のデータ構造が必要である。
素集合森
素集合森 (disjoint-set forest) はそれぞれの集合を木構造で表したデータ構造で、各ノードには親ノードへの参照がある。1964年、Bernard A. Galler と Michael J. Fischer が考案したが[2]、詳細な解析にはその後何年かかかった。
素集合森では、各集合の代表は木構造の根となる。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
この素朴な実装では、連結リストを使った場合と変わらない。なぜなら、木構造の平衡が保たれないからである。しかし、これを改善する方法が2つある。
第一の方法は union by rank と呼ばれ、Union操作で常に大きい木の方が全体の根になるように連結するものである。木の大きさを評価するにはrank を用いる。これは、1要素の木の rank を 0 とし、同じ rank r の木を連結したとき、全体の根とした方の木の rank を r+1 とするものである。このようにするだけで、MakeSet、Union、Find 操作の償却実行時間は 
カテゴリ
- 素集合データ構造のページへのリンク
