素集合連結リスト
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/10/07 05:02 UTC 版)
「素集合データ構造」の記事における「素集合連結リスト」の解説
素集合データ構造を生成する単純な手法としては、集合毎に連結リストを生成する方法がある。リストの先頭の要素がその集合の代表となる。 MakeSetは1要素のリストを生成する。Unionは2つのリストを連結する操作で、定数時間の操作である。この実装の欠点は、FindがΩ(n)または線形時間を必要とする点である。 これを防ぐには、連結リストの各ノードにそのリストの先頭へのポインタを格納しておけばよい。つまり、Findの引数がノードへのポインタであれば、即座にそのノードが属するリストの先頭（代表）がわかる。しかし、このように実装すると今度はUnion操作で各ノードの先頭へのポインタを更新しなければならなくなり、Ω(n) の時間がかかるようになる。 各リストの長さがわかっているなら、短い方を長い方に連結することでUnionの性能を改善できる。これ (weighted-union heuristic) を採用すると、n個の要素について、m回のMakeSet、Union、Find操作を行ったときにかかる時間は O(m + nlog n) となる。漸近的により高速な操作には別のデータ構造が必要である。
※この「素集合連結リスト」の解説は、「素集合データ構造」の解説の一部です。
「素集合連結リスト」を含む「素集合データ構造」の記事については、「素集合データ構造」の概要を参照ください。
ウィキペディア小見出し辞書の「素集合連結リスト」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 素集合連結リストのページへのリンク
