问题标签 [union-find]

我正在尝试在 Cormen 等人的算法简介中做这个练习，这与 Disjoin Set 数据结构有关：

假设我们希望添加操作PRINT-SET(x)，给定一个节点并以任意顺序x打印 集合的所有成员。x展示我们如何向不相交集森林中的每个节点添加一个属性，从而使PRINT-SET(x)时间与的集合的成员数成线性关系x，并且其他操作的渐近运行时间保持不变。假设我们可以在 O(1) 时间内打印出集合中的每个成员。

现在，我很确定需要的属性是一个尾指针，所以它可以跟踪孩子。

由于不相交的集合结构已经有一个父属性，find-set(x)可以很容易地打印出一个方向的节点。但是现在，有了一个尾指针，让我们也转向另一个方向。

但是，我不确定如何编写算法来做到这一点。如果有人可以用伪代码帮助我，那将不胜感激。

我正在使用一种union-find算法。在我的程序的第一部分，算法计算一个大集合的一个分区E。

之后，我想检索S包含给定节点的集合的所有成员x。

直到现在，我天真地测试E了 set的所有元素的成员资格S。但是昨天我正在阅读“算法简介”（CLRS，第 3 版，ex. 21.3-4），并且在练习中，我发现：

假设我们希望添加操作PRINT-SET(x)，给定一个节点并以任意顺序x打印 集合的所有成员。x展示我们如何向不相交集森林中的每个节点添加一个属性，从而使PRINT-SET(x)时间与x的集合成员数成线性关系，并且其他操作的渐近运行时间保持不变。

“与集合的成员数量成线性关系x”对我的问题将是一个很大的改进！所以，我正在尝试解决这个问题......经过一些不成功的尝试后，我在 Stack Overflow 上寻求帮助！

我在图中找到不相交集的数量，G然后删除图的一些顶点G并制作图G'，我想在其中找到不相交集的数量G'，是否有任何好的算法不做与G'我们一样的事情到G？

这个星期天我要考试，我只是想确认我所做的是否正确（你知道考试让我怀疑）

这是算法的工作原理：

这是问题：

回想一下为一组 n 个元素的不相交集上的 Union-Find 问题开发的算法。Find 使用路径压缩，Union 使用排名。此外，相同等级的两棵树的联合选择与第二个参数关联的根作为新根。从集合 S = {1, 2, ..., 10} 和 10 个不相交的子集开始，每个子集包含一个元素。一个。执行后绘制最后一组树：
Union(1,2)、Union(3,4)、Union(5,6)、Union(1,5)、Union(1,3)。

这是我对这个问题的解决方案：

我很想有关于这个算法的任何提示或建议。

谢谢！

我正在Coursera 上进行算法课程，作者在其中提到以下部分

带有路径压缩的加权快速联合的运行时间在现实世界中将是线性的，实际上可以改进为一个更有趣的函数，称为 Ackermann 函数，它比 lg 增长得更慢。关于这一点的另一点是，这似乎非常接近于线性，即时间与 N 成正比，而不是时间与 N 乘以 N 中缓慢增长的函数成正比。是否有一个简单的线性算法？人们为此寻找了很长时间，实际上我们可以证明没有这样的算法。（重点补充）

（你可以在这里找到完整的成绩单）

在包括维基百科在内的所有其他来源中，当时间与输入大小成比例增加时，使用“线性”，而在带有路径压缩的加权快速联合中，情况肯定不是这样。

这里的“现实世界中的线性”到底是什么意思？

我正在从这里http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests（它与 CLRS 中的伪代码几乎相同）通过排名和路径压缩来查看 UnionFind 的实现并且不明白为什么路径压缩不会改变排名。如果我们要求find从根开始的最长路径的端点，则排名应该下降，如果没有，下一个union操作将选择不正确的根。

这是我试图回答的一个面试问题：

给定一个包含成员的社交网络和一个包含成员对形成友谊N的时间戳的日志文件，设计一个算法来确定所有成员连接的最早时间（即，每个成员都是朋友的朋友的朋友。 M..朋友的）。假设日志文件按时间戳排序，友谊是等价关系。您的算法的运行时间应该是M log N或更好，并使用与 成比例的额外空间N。

我想到的第一件事是......“我不能这样做！”。

但后来我想，这个社交网络怎么能用数据结构来表达。Union-find 是一种可以使用的数据结构。现在我必须明白所有成员都连接起来意味着什么。我如何查看实际的数据结构以及每个成员彼此成为朋友时的样子？

我认为只有在我能够从视觉上或概念上理解系统如何完全连接之前，我才能开始弄清楚如何找到与该事件对应的时间戳。

通常，当我使用联合查找时，我会创建一个一维数组，并使用其在数组中的位置初始化每个索引处的值。因此，对于一个 5 元素数组，每个元素都将具有与其索引 ( ) 相同的值0-4。

如果我使用联合查找具有多个维度的数据结构，则变得更加困难。假设我有一个 10x10 站点的网格，每个站点最初都是关闭的（一个多维数组，每个索引都有 value -1）。我的实现提供了一种打开站点的方法，您可以在其中指定数组的维度。open(4, 3)将转到第 4 行并打开网格上的第 3 个站点。如果我要打开这个网站，我会给索引什么值，以及如何？

我在想我给它相对于第一个站点的位置的独特价值。因此，位置处的站点(4, 3)将被赋予值 43（向下 4 行，每行 10 个站点 + 右侧三个站点）。但这需要遍历每个站点并计算每个元素以获取将存储的值，即O(n). 我可以将4and转换3为字符串并将它们组合起来，但这是一个讲座的练习，我认为这不是他们希望我们做的。

此外，在网格上连接两个站点时，我遇到了同样的问题。如何确定代表连接的值而不通过大多数数组来查找它们的索引？

有没有更好的方法来做我正在尝试的事情？

我正在尝试为 Kruskal 实施联合查找算法。我正在使用这个伪代码，我不理解下面的联合部分 step2（它不是递归调用），或者我什至很接近。如果这种方式不起作用，只要我理解它，我可以使用任何实现。提前谢谢。U 和 V 是我的边缘节点，现在只是整数。

我不明白第 2 步，到目前为止，这是我的代码：

我正在寻找支持联盟功能的不相交集。

树木减高技术：

我们总是将较小的树合并到较大的树上，即我们使较小树的根指向较大树的根。

如果一棵树有更多的节点，它就比另一棵树大。

每个节点都是一个带有字段的结构体：元素的一些信息、指向父节点的指针“parent”和一个计数器“count”，仅当节点是根节点并且包含在上树。

以下算法合并两个向上树：

考虑使用联合的不相交集的实现，其中最多可以有 k 个不相交集。该实现使用哈希表 A[0.. max-1]，其中存储了基于排序双哈希方法的键。设 h1 和 h2 分别为主要和次要散列函数。A 包含上述所有树的节点的键，以及指向每个树的相应节点的指针。我想编写一个算法，将两个节点的键作为参数并合并节点所属的向上树（节点可以属于任何向上树，即使在这种情况下，它也会出现适当的消息） . 在合并时，我们应该应用路径压缩和高度降低的技术。

你能给我一个提示，我们怎么能做到这一点？

假设我们有这个数组：

一开始的节点会是这样的：

那么如果k1=100，k2=5，应用算法后，我们会得到这个吗？

那么如果我们有 k1=59, k2=5，我们将得到以下结果：

正确的？然后应用路径压缩，我们开始这样做：

所以我们将有 parent=F, tmp->parent=B, tmp=F。

我们如何继续？

然后 k1=14, k2=59 我们得到：