"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"：

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

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

统合子集：

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

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

可视化数据结构：

范围  (1)

信息  (1)

可用 CreateDataStructure 创建新的 "DisjointSet"：

数据结构 ds 的信息：

应用  (1)

Kruskal 算法  (1)

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

实现 Kruskal 算法：

用来测试 Kruskal 算法的图：

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

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