"DisjointSet" (データ構造)

"DisjointSet"

一般式であり，互いに素な集合に分割される要素の集合を表す．

詳細

  • 互いに素な集合には，効率的なマージと削除，およびメンバシップの検証が行える．
  • CreateDataStructure[ "DisjointSet"]新しい空の"DisjointSet"を作成する
    Typed[x,"DisjointSet"]x に"DisjointSet"型を与える
  • "DisjointSet"型のデータ構造には，以下の演算が使える．
  • ds["CommonSubsetQ",x,y]x と y が同じ部分集合に含まれる場合にTrueを返すtime: O(α(n))
    ds["Copy"]ds のコピーを返すtime: O(n)
    ds["Delete",x]x を ds から削除し，x が実際に要素である場合にはTrueを返すtime: O(n)
    ds["Elements"]ds の要素のリストを返すtime: O(n)
    ds["EmptyQ"]ds が空の場合にはTruetime: O(1)
    ds["Find",x]x の親を返すtime: O(α(n))
    ds["Insert",x]x を要素の集合に加えるtime: O(α(n))
    ds["InsertAll",elems]要素 elems を要素の集合に加えるtime: O(α(n) nelems)
    ds["Length"]ds に保存される要素の数を返すtime: O(1)
    ds["MemberQ",x]x が ds の要素である場合にTrueを返すtime: O(1)
    ds["Merge",dsi]dsi の要素をinto ds に結合するtime: O(n)
    ds["Subsets"]ds の部分集合を返すtime: O(n)
    ds["Unify",x,y]x と y の部分集合を統合するtime: O(α(n))
    ds["UnifyAll",elems]elems の要素の部分集合を統合するtime: O(α(n) nelems)
    ds["Visualization"]ds の可視化を返すtime: O(n)
  • 以下の関数もサポートする．
  • dsi===dsjdsi が dsj に等しい場合はTrue
    FullForm[ds]ds の完全形
    Information[ds]ds についての情報
    InputForm[ds]ds の入力形
    Normal[ds]ds を通常の式に変換する
  • 一般的な部分集合における挿入，マージ，検証等の演算の多くは，ほぼ一定の時間で行われ，α(n)，逆アッカーマン関数で有界である．

例題

すべて開くすべて閉じる

例  (1)

新しい"DisjointSet"は，CreateDataStructureを使って作成できる：

最初は，要素も部分集合もない：

2つの要素をそれぞれ独自の部分集合に挿入する：

部分集合を統合する：

さらに2つの要素を加えて統合する．これで部分集合は2つになった：

2つの部分集合を統合する．これで部分集合は1つになった：

データ構造の可視化を生成することができる：

スコープ  (1)

情報  (1)

新しい"DisjointSet"は，CreateDataStructureを使って作成することができる：

データ構造 ds についての情報：

アプリケーション  (1)

クラスカル法  (1)

グラフの最小全域木は，すべての頂点含む木で，辺の重さの総和が最小のものである．クラスカル法は，最小全域木を計算する一つの方法であり，"DisjointSet"を使って書くことができる．

クラスカル法の実装：

クラスカル法の実装を検証するために使うグラフ：

クラスカル法で最小全域木を計算する：

もとのグラフに最小全域木がどのようにマップされるかを示す：