|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 素 ： [もと] 1. (n,n-suf,n-t) (1) origin 2. basis 3. foundation ・ 集 ： [しゅう] 【名詞】 1. collection ・ 集合 ： [しゅうごう] 1. (n,vs) (1) gathering 2. assembly 3. meeting 4. (2) (gen) (math) set ・ 合 ： [ごう] 【名詞】 1. go (approx. 0.18l or 0.33m) ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 構造 ： [こうぞう] 【名詞】 1. structure 2. construction
素集合データ構造（そしゅうごうデータこうぞう、英: 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'' + ''n''log ''n'') となる〔Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ''Introduction to Algorithms'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 21: Data structures for Disjoint Sets, pp.498–524.〕。漸近的により高速な操作には別のデータ構造が必要である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「素集合データ構造」の詳細全文を読む スポンサード リンク
|