structure)は、データの集合を素集合(互いにオーバーラップしない集合)に分割して保持するデータ構造。このデータ構造に対する以下の2つの便利な操作をUnion-Findアルゴリズムと呼ぶ。特定の要素がどの集合に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。2つの集合を1つに統合する。これら2つの操作をサポートしているため、素集合データ構造は「Union-Findデータ構造」あるいは「Merge-Find集合」とも呼ばれる。MakeSetがある。これは、与えられた1つの要素だけを格納した集合(シングルトン)を作成する。これら3つの操作により、様々な実用的分割問題を解くことができる(「応用」の節を参照)。これらの操作をより正確に定義するには、集合の表現方法を決める必要がある。(representative)」とし、その集合全体を表すものとする。属する集合の代表を返す。2つの代表を引数とする。素集合連結リスト[編集]素集合データ構造を生成する単純な手法としては、集合毎に連結リストを生成する方法がある。リストの先頭の要素がその集合の代表となる。MakeSetは1要素のリストを生成する。Unionは2つのリストを連結する操作で、定数時間の操作である。この実装の欠点は、FindがΩ(n)または線形時間を必要とする点である。これを防ぐには、連結リストの各ノードにそのリストの先頭へのポインタを格納しておけばよい。Findの引数がノードへのポインタであれば、即座にそのノードが属するリストの先頭(代表)がわかる。時間がかかるようになる。各リストの長さがわかっているなら、短い方を長い方に連結することでUnionの性能を改善できる。漸近的により高速な操作には別のデータ構造が必要である。それぞれの集合を木構造で表したデータ構造で、各ノードには親ノードへの参照がある。考案したが[2]、詳細な解析にはその後何年かかかった。素集合森では、各集合の代表は木構造の根となる。Findは親ノードへのリンクを根に到達するまでたどっていく。Unionは2つの木構造を1つにする操作であり、どちらかの根が全体の根となる。以下に素集合森の実装例を擬似コードで示す。yRootこの素朴な実装では、連結リストを使った場合と変わらない。木構造の平衡が保たれないからである。これを改善する方法が2つある。呼ばれ、Union操作で常に大きい木の方が全体の根になるように連結するものである。