Apache Spark上的不相交集合
我正在尝试找到使用Apache Spark在大量数据上搜索不相交集合(连接组件/并查集)的算法。问题在于数据量很大，即使是图形顶点的原始表示形式也无法适应单个计算机的内存，边缘也不能满足内存要求。 源数据是HDFS上的图形边缘文本文件: "id1 \ tid2"。 id以字符串值而非整数表...
实施Kruskall算法时如何测试电路
我正在尝试编写一个能够寻找最小生成树的程序。但是，这个算法遇到了一个问题，就是如何测试电路。在Java中，最好的方法是什么呢。 好的，这是我的代码： import java.io.*; import java.util.*; public class JungleRoads { ...
Union+Find算法（不相交集合）的应用
问题陈述： 方程的格式为 A / B = k，其中 A 和 B 是用字符串表示的变量，k 是一个实数（浮点数）。 给定一些查询问题，返回答案。如果答案不存在，则返回 -1.0。 例如：给定 a / b = 2.0, b / c = 3.0. 查询问题为：a / c = ?, b / a...
在C++中实现等价关系（使用boost::disjoint_sets）
假设您有许多元素，需要跟踪它们之间的等价关系。如果元素A等价于元素B，则它等价于所有其他元素，这些元素与B等价。 我正在寻找一种有效的数据结构来编码此信息。应该可以通过与现有元素的等价性动态添加新元素，并且从该信息中应该能够有效地计算新元素等价于哪些元素。 例如，考虑以下元素[0,1,2,...
理解boost::disjoint_sets
我需要使用boost::disjoint_sets，但文档对我来说不太清晰。请有人解释一下每个模板参数的含义，并为创建disjoint_sets给出一个小例子代码吗？ 根据要求，我正在使用disjoint_sets来实现Tarjan离线最近公共祖先算法，即-值类型应该是vertex_desc...
在线性时间内打印不相交集合数据结构中的节点
我正在尝试完成Cormen等人的算法导论中与不相交集数据结构有关的练习： 假设我们希望添加操作PRINT-SET（x），它接收一个节点x并以任意顺序打印x集合中的所有成员。展示如何仅向不相交集森林中的每个节点添加单个属性，以便PRINT-SET（x）需要时间线性地执行x集合的成员数量，并且其...
如何在联通组件标记中使用不相交集合？
我在使用连通组件标记中遇到了使用不连通集合的困难。我已经查看了许多示例，还查看了此问题，其中Bo Tian提供了一个非常好的C++链接列表作为不连通集合的实现。我已经在程序中实现了连接组件标记（标签是简单的整数），但我很难解决不连通集合中标签之间的等价关系。 有人能帮我解决这个问题吗？也许可...
路径压缩和按秩合并如何互相补充？
我一直在研究并查集问题。两个主要的改进是路径压缩和按秩合并。据我所知，按秩合并用于确定如何组合不相交的树。如果我们有两棵不相交的树T1和T2，那么我们将较小秩的树的根节点连接到较大秩的树上。如果我们不使用路径压缩，则秩仅为树的深度。这是有道理的，因为我们不想增加树的深度，因为它直接影响查找和合...
Python中的不相交集合实现
我对Python比较陌生。我正在学习并实现“不相交集合”：class DisjointSet: def __init__(self, vertices, parent): self.vertices = vertices self.parent = pa...
用C++实现不相交集合（并查集）
我正在尝试实现不相交集并查集，用于Kruskal算法，但是我不太明白应该如何实现，特别是如何管理森林中的树。在阅读了维基百科上对于不相交集描述以及《算法导论》（Cormen等人）中的描述后，我得出了以下代码： class DisjointSet { public: ...