WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

"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を使って作成できる：

Wolfram Language code: ds = CreateDataStructure["DisjointSet"]

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

Wolfram Language code: ds["Subsets"]

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

Wolfram Language code: ds["Insert", f[1]]; ds["Insert", f[2]]; ds["Subsets"]

部分集合を統合する：

Wolfram Language code: ds["Unify", f[1], f[2]]; ds["Subsets"]

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

Wolfram Language code: ds["Insert", f[3]]; ds["Insert", f[4]]; ds["Unify", f[3], f[4]]; ds["Subsets"]

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

Wolfram Language code: ds["Unify", f[1], f[4]]; ds["Subsets"]

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

Wolfram Language code: ds["Visualization"]

スコープ  (1)

情報  (1)

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

Wolfram Language code: ds = CreateDataStructure["DisjointSet"]

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

Wolfram Language code: Information[ds]

アプリケーション  (1)

クラスカル法  (1)

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

クラスカル法の実装：

Wolfram Language code: Kruskal[gr_ ? EdgeWeightedGraphQ] := Module[{a = {}, ds}, ds = CreateDataStructure["DisjointSet"]; Do[ds["Insert", vert], {vert, VertexList[gr]}]; Do[ If[ds["Find", First[edge]] =!= ds["Find", Last[edge]], AppendTo[a, edge];ds["Unify", First[edge], Last[edge]] ], {edge, SortBy[EdgeList[gr], AnnotationValue[{gr, #}, EdgeWeight]&]} ]; TreeGraph[a, VertexLabels -> Automatic] ]

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

Wolfram Language code: g = [image];

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

Wolfram Language code: st = Kruskal[g]

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

Wolfram Language code: HighlightGraph[g, st, GraphHighlightStyle -> "Thick"]