问题标签 [disjoint-sets]

我碰巧在维基百科上读到，在不相交集（联合两个元素，找到特定元素的父元素）上每次操作的摊销时间是 O(a(n))，其中 a(n) 是逆阿克曼函数，它会增长非常快。

谁能解释为什么这是真的？

谁能给我指出一些关于不相交集的信息作为链表？我找不到任何代码。语言 C++

我知道 STL 有set_difference，但我只需要知道 2 sets 是否不相交。我已经分析了我的代码，这大大降低了我的应用程序的速度。有没有一种简单的方法可以查看 2 组是否不相交，或者我是否只需要滚动自己的代码？

编辑：我也试过set_intersection，但花了同样的时间......

刚研究了disjoint set数据结构，知道它也叫“union-find数据结构”，union和find是这个数据结构的两个主要操作。我们可以对不相交的集合进行并集，类似地我们可以进行查找操作；我想知道除了 union 和 find 之外，我们还可以对不相交的集合执行哪些其他操作。

由于我们的老师只解释了联合和查找操作，我在 C++ 中实现不相交集 ADT 时遇到问题。我完全理解 union 和 find 的概念，但我仍然对如何实现它们感到困惑。

有人可以给我一个实现的想法，并解释这个数据结构的接口应该是什么样子吗？

以下是wikipedia上不相交集森林的联合/查找算法的细分：

• 准系统不相交的森林... ( O(n))
  • ...按等级联合...（现在改进为O(log(n)）
    • ... 带有路径压缩（现在改进为O(a(n)), 有效O(1)）

按等级实现联合需要每个节点保留一个rank字段以进行比较。我的问题是，按等级联合是否值得这个额外的空间？如果我按等级跳过联合而只进行路径压缩会发生什么？够好吗？现在的摊销复杂度是多少？

做了一个评论，暗示没有路径压缩（摊销O(log(n)复杂性）的按等级联合对于大多数实际应用来说已经足够了。这是对的。我要问的是另一种方式：如果您按等级跳过联合并且只进行路径压缩怎么办？

从某种意义上说，路径压缩是按等级改进联合的额外步骤，这就是为什么可以省略该额外步骤而不会造成灾难性后果的原因。但是按等级联合是路径压缩的必要中间步骤吗？我可以跳过它并直接进行路径压缩，还是会是灾难性的？

还有人指出，如果没有按等级联合，重复联合可以创建类似链表的结构。这意味着单路径压缩操作可能会O(n)在最坏的情况下进行。这当然会影响未来的运营，所以当摊销到许多运营中时，这将如何发挥作用是我更感兴趣的。

我无法理解下图：

为什么A链接到D而不是B？为什么 C 链接到 F 而不是 D？

今天，由于这张幻灯片的第 13 页，我与某人讨论了 Kruskal 最小生成树算法。

该演示文稿的作者说，如果我们使用（双）链表实现不相交集，则性能为Make和Find的性能将分别为O(1)和O(1)。运算Union(u,v)的时间为min(nu,nv)，其中nu和nv是存储 u 和 v 的集合的大小。

我说过我们可以通过使每个成员的表示指针指向一个包含指向集合的真实表示的指针的定位器来将Union(u,v)的时间缩短为O(1) 。

在 Java 中，数据结构如下所示：

对不起，简约的代码。如果可以这样制作，那么每个不相交集操作（Make,Find,Union）的运行时间将是O(1)。但与我讨论过的人看不到改进。我想知道你对此的看法。

Find/Union 在各种实现中的最快性能是什么？我不是数据结构方面的专家，但是通过在互联网上快速浏览，我发现没有恒定时间数据结构或算法可以做到这一点。

假设你有很多元素，你需要跟踪它们之间的等价关系。如果元素 A 等价于元素 B，则它等价于 B 等价的所有其他元素。

我正在寻找一种有效的数据结构来编码这些信息。应该可以通过与现有元素的等价来动态添加新元素，并且从该信息中应该可以有效地计算新元素等价的所有元素。

例如，考虑以下元素 [0,1,2,3,4] 的等价集：

其中等号表示等价。现在我们添加一个新元素5

并强制等价5=3，数据结构变为

由此，人们应该能够有效地迭代任何元素的等价集。对于 5，这个集合是 [3,4,5]。

Boost 已经提供了一个方便的数据结构disjoint_sets，它似乎可以满足我的大部分要求。考虑这个说明如何实现上述示例的简单程序：

如上所示，可以有效地添加元素，并动态扩展不相交的集合。如何有效地迭代单个不相交集合的元素，而不必迭代所有元素？

我需要使用 boost::disjoint_sets，但我不清楚文档。有人可以解释每个模板参数的含义，也许可以提供一个创建disjoint_sets的小示例代码吗？

根据请求，我正在使用 disjoint_sets 来实现Tarjan 的离线最小公共祖先算法，即 - 值类型应该是 vertex_descriptor。