WOLFRAM

Wolfram 语言与系统参考资料中心

"DisjointSet" （数据结构）

"DisjointSet"

表示元素的集合，这些元素是一般表达式并且被划分为不相交的集合.

更多信息

  • 不相交的集合可有效处理合并、删除以及成员测试操作：
  • CreateDataStructure[ "DisjointSet"]创建新的空 "DisjointSet"
    Typed[x,"DisjointSet"]指定 x 的类型为 "DisjointSet"
  • 对于类型为 "DisjointSet" 的数据结构，可进行以下操作：
  • ds["CommonSubsetQ",x,y]如果 x 和 y 在同一个子集中则返回 True时间：O(α(n))
    ds["Copy"]返回 ds 的副本用时：O(n)
    ds["Delete",x]从 ds 中删除 x，如果 x 是元素，返回 True用时：O(n)
    ds["Elements"]返回 ds 的元素列表用时：O(n)
    ds["EmptyQ"]如果 ds 为空则给出 True用时：O(1)
    ds["Find",x]返回 x 的父集合用时：O(α(n))
    ds["Insert",x]把 x 添加到元素的集合中用时：O(α(n))
    ds["InsertAll",elems]将元素 elems 添加到元素集合中用时：O(α(n) nelems)
    ds["Length"]返回存储在 ds 中的元素的数量用时：O(1)
    ds["MemberQ",x]如果 x 是 ds 的元素则返回 True用时：O(1)
    ds["Merge",dsi]将 dsi 的参数合并到 ds 中用时：O(n)
    ds["Subsets"]返回 ds 的子集用时：O(n)
    ds["Unify",x,y]统合 x 和 y 的子集用时：O(α(n))
    ds["UnifyAll",elems]统一 elems 中元素的子集用时：O(α(n) nelems)
    ds["Visualization"]返回 ds 的可视化用时：O(n)
  • 还支持以下函数：
  • dsi===dsj如果 dsi 等于 dsj 则为 True
    FullForm[ds]ds 的完全形式
    Information[ds]关于 ds 的信息
    InputForm[ds]ds 的输入形式
    Normal[ds]将 ds 转换成普通表达式
  • 对常见子集的许多操作（如插入、合并和测试）为常量时间操作，并受逆 Ackermann 函数 α(n) 限定.

范例

打开所有单元 关闭所有单元

基本范例  (1)

可用 CreateDataStructure 创建新的 "DisjointSet"：

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

开始时没有元素，也没有子集：

Wolfram Language code: ds["Subsets"]

插入两个元素；分别归入自己的子集：

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

统合子集：

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

再添加两个元素并统合；现在有两个子集：

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

统合两个子集；现在只有一个子集：

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

可视化数据结构：

Wolfram Language code: ds["Visualization"]

范围  (1)

信息  (1)

可用 CreateDataStructure 创建新的 "DisjointSet"：

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

数据结构 ds 的信息：

Wolfram Language code: Information[ds]

应用  (1)

Kruskal 算法  (1)

图的最小生成树是一棵以最小的总边权重连接所有顶点的树. Kruskal 算法是一种计算最小生成树的方法，可用 "DisjointSet" 来实现.

实现 Kruskal 算法：

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] ]

用来测试 Kruskal 算法的图：

Wolfram Language code: g = [image];

用 Kruskal 算法计算最小生成树：

Wolfram Language code: st = Kruskal[g]

显示最小生成树如何映射到原始的图：

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