问题标签 [union-find]

我正在尝试解决以下算法问题：

假设我们有一个数据结构，允许我们插入元素并删除和写入最小元素。假设我们知道一系列n命令，所有这些命令要么是I(k)（插入 k）要么是D（删除最小值并输出它）。

我们的任务是为每个D命令决定它将返回哪个数字。例如，对于序列：

结果应该是

目标（或提示）是比复杂性更好O(nlog(n))，使用 Find-Union 数据结构，它允许我们在 中进行nmake-sets、finds 和 unions O(na(n))，其中a(n)是逆 Ackermann 函数。

这不是家庭作业 - 我正在准备考试，并且已经在这个练习中遇到了几个多小时的困难。

我将不胜感激任何进一步的提示

编辑：我忘了添加一个关键假设。我们插入的所有数字都来自范围 1..n

进一步编辑：事实证明我不是第一个遇到这个问题的人；它被称为离线最小问题，任何有兴趣的人都可以在此处进一步阅读

我有一个带有权重的边列表，我想从中获取不相交的集合。但是，我也想跟踪集合中的权重。例如，如果我有一个数据集，

这将导致两组

本质上，关系中的权重乘以权重。除了暴力破解之外，是否有任何有效的算法来跟踪这一点？选择的语言是python。

我知道一般如何实现联合查找，但我在考虑是否有办法利用 python 中的集合结构来实现相同的结果。例如，我们可以很容易地联合集合。但我不确定如何仅使用集合来确定两个元素是否在同一个集合中。所以，我想知道除了通常的实现之外，python 中是否有支持这种操作的数据结构？

我查看了其他类似的问题，但无法弄清楚这个错误的原因。我正在编写一个 C++ 程序来实现 Kruskal 的最小生成树算法，使用 Union by rank 和路径压缩。它正确打印 MST 的边缘，但包含路径压缩部分会导致此错误：

* `./kruskal' 中的错误：free()：无效指针：0x0000000001650d00 *

通过查看 gdb 的回溯，它似乎是向量/类析构函数的问题：

有人可以解释一下当我在循环中包含路径压缩时会发生什么中断吗？

编辑：给出错误的示例输入：

我正在使用联合查找算法来查找无向图的所有连通分量。由于某些未知原因，它给出了错误的答案。我给出的输入图是连接的，但它为该图输出了 2 个不同的标签。

如果有人能解释这个异常，我会很高兴。是否存在一些特殊的无向图，Union-Fid 可能不起作用？

** 图表有点大，所以我添加了一张图片以提高图表的可读性。无法修剪图表，否则问题的本质将消失。**

这里，p 和 rk 分别是父级和排名。

代码

联合函数

查找功能

样本输入

图表照片

请注意，我没有考虑节点 1、2、3 和 18 及其边缘。

无向图

我对算法的理解是这样的......

• 路径压缩有助于缩短查找操作的时间，并且超时路径压缩的时间复杂度平均为 O(1)。
  

• 我们决定两者中的哪一个是父节点（在联合操作期间）查看排名。

但是我永远无法理解等级联盟的作用，我不相信我正确理解等级在这里的含义。我也不明白为什么在联合期间，如果要联合的两组的等级相同，则父级的等级增加 1。

有人可以用粗体解释答案吗？它是怎么做的？

下面是四个联合查找操作的序列（带有加权联合和完全压缩），它们导致了以下向上树。最后两次操作是什么？

答案：Union(D,A)，Union(B,C)，Union(D/A,B/C)，Find(B/C)。

我试图理解boost::disjoint_sets_with_storage但即使是最简单的例子也不起作用，我不明白为什么。

上面的代码可以编译，但会产生段错误。我想使用整数作为元素，但在boost 文档中没有“元素”模板参数，所以我假设它推断类型。但是，问题是什么？谢谢

我正在寻求改进我的解决方案，以使用快速查找算法在有向图中查找所有弱连接组件。

问题陈述

给定一个 列表DirectedGraphNode，找到所有岛（即弱连接组件）。

因此，给定以下有向图：

输出应该如下（顺序无关紧要）：

我使用快速查找算法解决了这个问题。下面的代码：

然而，这个算法在最坏的情况下运行在O(N^3)中，因为它每次都需要对联合进行线性搜索。我很好奇是否有任何方法可以改善这一点。

谢谢您的建议！

我正在学习联合/查找结构的“带路径压缩的加权快速联合”算法。普林斯顿教育网站详细解释了该算法。这是Java中的实现：

但就像网站提到它的性能一样：

定理：从一个空数据结构开始，对 N 个对象的任何 M 个 union 和 find 操作序列都需要 O(N + M lg* N) 时间。

• 证明非常困难。

• 但算法仍然很简单！

但是我还是很好奇迭代对数lg*n是怎么来的。它是如何派生的？有人可以证明它还是以直观的方式解释它？