问题标签 [disjoint-sets]

我试图找到使用 apache spark 在大量数据上搜索不相交集（连接组件/联合查找）的算法。问题是数据量。甚至图形顶点的原始表示也不适合单机上的 ram。Edges 也不适合 ram。

源数据是 hdfs 上图形边缘的文本文件：“id1 \t id2”。

id 以字符串值的形式出现，而不是 int。

我发现的幼稚解决方案是：

1. 取边的 rdd ->[id1:id2] [id3:id4] [id1:id3]
2. 按键分组边缘。->[id1:[id2;id3]][id3:[id4]]
3. 对于每个记录集的每个组的最小 id ->(flatMap) [id1:id1][id2:id1][id3:id1][id3:id3][id4:id3]
4. 从第 3 阶段反转 rdd[id2:id1] -> [id1:id2]
5. leftOuterJoin来自第 3 阶段和第 4 阶段的 rdds
6. 从第 2 阶段重复，而第 3 步中 rdd 的大小不会改变

但这会导致节点之间传输大量数据（洗牌）

有什么建议吗？

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

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

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

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

我正在编写代码以在图表上执行联合查找，

输入的第一行是：
nm [n是节点数，m是边数]

然后是m行，表示连接了哪两个节点

当我遇到每条边时，我会执行联合操作来连接节点。执行并集后，我还想知道最大子集和最小子集的大小

到目前为止，这是我的代码，

我正在使用蛮力来获得最小尺寸的子集和最大尺寸的子集。此代码在 Sphere Online Judge 中超时。

获得最小尺寸子集和最大尺寸子集的更有效方法是什么。

SPOJ 问题链接是：http ://www.spoj.com/problems/LOSTNSURVIVED/

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

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

我现在正在学习在线数据结构课程。这是我的合并和查找算法的 Python 实现。我按照说明进行操作，但运行时间远远超出了限制。任何人都可以看看吗？它应该是一个简单的。谢谢。

我们必须进行“m”合并或联合操作。() 和 () 是两个有真实数据的表的编号。如果（）̸=（），将表（）中的所有行复制到表（）中，然后清除表（），而不是实际数据，将（）的符号链接放入其中。答案是列表行的最大表格大小。操作顺序示例：

输入显示有 5 个表，我们要做 5 次操作。每个表的大小为 1。以下五行表明我们要将 source5 合并到destination3，将source4 合并到destination2...输出应该是：

说明：在此示例中，所有表最初都只有 1 行数据。考虑合并操作：

1. 表 5 中的所有数据都复制到表 3。表 5 现在只包含指向表 3 的符号链接，而表 3 有 2 行。2 成为新的最大尺寸。

2. 2 和 4 以与 3 和 5 相同的方式合并。

3. 我们试图合并1和4，但是4有一个符号链接指向2，所以我们实际上把2号表的所有数据复制到1号表，清空2号表并放一个符号链接到表其中排名第一。表 1 现在有 3 行数据，3 成为新的最大大小。

4. 从4遍历符号链接的路径我们有4→2→1，而从5的路径是5→3。所以我们实际上是合并表3和1。我们将表号1的所有行复制到表号中3，现在3号表有5行数据，是新的最大值。

5. 现在所有表都直接或间接指向表 3，因此所有其他合并不会改变任何内容。

说明：思考如何使用带路径压缩的不相交集并集和秩启发式并集来解决这个问题。特别是，您应该将执行联合/查找操作的数据结构与表的合并区分开来。如果要求将第一个表合并到第二个，但是第二个表的rank小于第一个表的rank，在Disjoint Set Union数据结构中合并时可以忽略请求的顺序，加入对应的节点到第二个表到与第一个表对应的节点，而不是在你的不相交集联合中。但是，您需要将请求合并第一个表的实际第二个表的编号存储在相应不相交集的父节点中，

这是我使用秩启发式和路径压缩来实现它的代码：

是否有任何算法或代码将图节点划分为两个或多个满足以下条件的不相交集：首先，只允许删除边。其次，对边缘进行加权，并且那些将被删除的边缘必须具有最小权重（最小切割算法）。第三，期望的不相交集尽可能长。

我知道前者是一种数据结构，而后者是一种数学结构。

但在实施时，它们似乎具有许多相同的特性和行为。

不相交集中的每个元素都可以被认为是图中的一个顶点。图中的边表示 Union-Find 中的集合。

在查看http://algs4.cs.princeton.edu/15uf/和http://algs4.cs.princeton.edu/42digraph/

我相信两者都可以回答以下问题：

• 这两个元素/顶点是否连接？
• 有循环吗？

那么我没有看到的两者之间有更大的区别吗？我什么时候应该选择使用其中一种？

我看到图形算法可以在内部使用 Union-Find 结构 http://algs4.cs.princeton.edu/43mst/KruskalMST.java.html

一个实现细节，但如果联合查找更快，为什么要使用深度优先搜索来测试循环？http://algs4.cs.princeton.edu/44sp/DirectedCycle.java.html

我一直在阅读有关联合查找问题的信息。两个主要改进是路径压缩和按等级联合。据我了解，按等级联合用于确定如何组合不相交的树。如果我们有两棵不相交的树 T1 和 T2，那么我们将具有较小等级的树的根附加到具有较高等级的树上。如果我们不使用路径压缩，那么排名只是树的深度。这是有道理的，因为我们不想增加输出树的深度，因为它直接影响查找和联合。

我的问题是当我们也使用路径压缩时。我一直在读到这两种优化相辅相成，但我没有看到。由于路径压缩，排名不再是树的深度（它成为深度的上限）。假设 T1 有 2 个分支（设 T1 的 rank 为 3），T2 的深度为 2，rank 为 2。现在假设我们在下面标有“*”的 T1 的叶子上执行查找操作（带有路径压缩）。现在，如果我们联合 T1 的根和 T2 的根，那么 T2 将附加到 T1 的根（因为查找不会更新排名）。结果树的深度为 3。但如果我们将 T1 附加到 T2，我们可能会有更好的性能。

在 T1("*") 的叶子上找到后，然后在 T1 和 T2 的根上并集，我们得到

我在这里错过了什么吗？路径压缩和按等级联合如何相互补充？我知道等级只是树深度的上限，但我看不出按等级联合如何提高结构的整体性能。这比随机组合根的联合更好吗？

我在这里先向您的帮助表示感谢。

计算查找增广路径的最简单方法是什么？

使用标记遍历计算边缘不相交路径以查找增强路径

我可以使用我的while循环来完成吗？如何？

我在在线比赛中遇到了这个问题，我正在尝试使用不相交集数据结构来解决它。

问题定义：

鲍勃在学校旅行期间参观了一座核电站。他观察到工厂中有 n 根核棒，核棒的初始效率为 1。一段时间后，核棒开始相互融合并结合形成一个群。这个过程将核棒的效率降低到组大小的平方根。Bob 是一个好奇的学生，他想知道一段时间后核电站的总效率。这是通过增加组的效率来获得的。

最初所有的棒都属于它自己的大小为 1 的组。有 f 个融合。如果 rod1 和 rod2 融合，则意味着它们的组融合了。

样本输入：

5 2

1 2

2 3

样本输出：

3.73

解释：

n=5 融合=2

组 1,2,3 => 1.73 (sqrt(3))

第 4 组 => 1

第 5 组 => 1

总计 = (1.73 + 1 + 1) = 3.73

我的代码：

上面的代码似乎适用于除一个之外的所有测试用例。

输入在这里，我的代码失败了。

预期输出为：67484.82

我的输出：67912.32

我真的无法弄清楚我哪里出错了，因为输入真的很大。

任何帮助将不胜感激。提前致谢。