问题标签 [disjoint-sets]

我正在尝试编写一个可以找到最小生成树的程序。但是我在使用这种算法时遇到的一个问题是测试电路。在java中执行此操作的最佳方法是什么。

好的，这是我的代码

我有一组类来处理我的 C++ 应用程序中的不相交集。我很难为这些类实现析构函数。任何人都可以帮助我吗？

这些基本上做的是：将nodes' 指针放入NodeAddress[]，每个node都由它来区分val。每个节点都有一个指向不相交集头部和尾部的Item占位符的指针。hdtl

我想提一下，我意识到存在一些问题，例如：变量可见性（公共访问）、恒定大小NodeAddress的缓冲区，但我想在这里关注内存释放。

是的，我想（需要）在指针上做（没有 STL）。如果您有任何建议或问题，请随时发表评论。

这是代码：

标题

资源

*编辑：* 我有一些东西但不工作

我正在用 Python 实现一个不相交的集合系统，但我碰壁了。我正在为系统使用树实现，并且正在为系统实现 Find()、Merge() 和 Create() 函数。

我正在实施等级系统和路径压缩以提高效率。

问题是这些函数必须将不相交的集合作为参数，使得遍历变得困难。

Create 函数接受一个值列表并返回一个包含适当数据的奇异节点列表。

我在想 Merge 函数看起来与此类似，

但我不确定如何实现 Find() 函数，因为它需要将节点列表和一个值（不仅仅是一个节点）作为参数。Find(set, value) 将是原型。

我了解当将节点作为 Find(x) 的参数时如何实现路径压缩，但是这种方法让我失望。

任何帮助将不胜感激。谢谢你。

为澄清而编辑。

我是图论的新手，到目前为止我只学习了图论中的 BFS 和不相交集。如果给定的无向连通图中存在一个循环，我可以使用 BFS 找到它吗？我的意图是打印循环中的所有顶点。提前致谢。

我正在尝试查找 freebase co-types，也就是说，给定一个您找到“兼容”类型的类型：

假设以 /people/person 开头，可能是音乐家 (/music/group_member)，但不是音乐专辑 (/music/album)，我不知道在 freebase 中是否有类似 owl 'disjointWith' 的东西类型，无论如何在他们建议使用这个技巧的 MQL 食谱中。

示例中的查询获取给定类型的所有实例，然后获取所有实例的所有类型并让它们唯一......这很聪明，但是查询超时......还有其他方法吗？对我来说，即使是静态列表/结果也可以，我不需要实时查询……我认为结果是一样的……

编辑： 不兼容的类型类型似乎很有用，类似于 disjointWith，也可以与建议一起使用...

谢谢！卢卡

在映射超类、子类关系

参与约束 - 部分不相交约束 - 不相交

我们是否必须将外键从孩子映射到父母？如果我们不这样做，为什么不呢？

我目前正在为处理城市和桥梁的任务编写代码。我必须在他们受人尊敬的地区打印城市和桥梁，例如：

运行程序后，排序为：

现在，我将通过 cin 读取这些输入。我想将所有可能的路径（例如 1 2 5）存储到一个数组中，然后通过程序对其进行排序和组织。问题是我可能有超过 500,000 条来自用户的路径。我想创建 500k 动态数组。这会导致内存方面的严重问题吗？

我已经研究了解决这个问题的其他可能方法，例如 kruskal 算法和不相交集（我认为是最有用的）。我很难理解不相交集的编码，我想我尝试一种我更熟悉的方式。

任何关于在哪里存储值以及比较和组织它们的帮助都会很棒。链接到我阅读这方面信息的地方会有所帮助。在过去的几天里，我读了很多书。没有多大帮助。

总结一下，我的问题是：

• 500k 的动态数组会不会在内存方面造成严重的问题？
• 在给定路径的情况下，在哪里存储值并比较和组织它们？

我在计算每个不相交的集合成员中的元素数量时遇到了一些麻烦。例如，如果有人输入：

注意：第一个数字 = 源顶点，第二个数字 = 目标顶点，第三个数字 = 长度

0 2 1

4 8 7

5 8 6

1 2 5

2 3 17

我将 2 作为集合的计数

4 8 7

5 8 6

和 3 作为集合的计数，因为两者都由 2 个和 3 个（各自的）元素连接。

0 2 1

1 2 5

2 3 17

我的想法是将每个不相交集的元素数存储到一个整数数组中，这样我就可以访问永远不相交集的计数。下面是我查找元素并将它们合并到同一个集合中的实现。我还有一个函数可以在每个集合中找到根。

我只是不确定在哪里/何时增加和维护我的计数器。任何帮助，将不胜感激。谢谢！

对于真正的大数据（例如超过 2^32 个元素和超过 2^32 对联合），是否有任何增强的不相交集算法？

显然最大的问题是我无法制作这么大的数组，所以我想知道是否有更好的算法或更好的数据结构来完成我的任务？

我已经有 N 个节点和 N-1 条边，基本上是无向无环 MST。我想基本上计算不相交的节点集的数量。如果两个节点具有相同的父节点并且节点的度数相同，则它们属于集合。例如。在给定的树中。{3,4} 属于同一个集合，因为parent[3]=1andparent[4]=1和degree[3]=degree[4]=1 ; {5} 和 {2} 也形成不相交的集合，因为 parent[2]=parent[5]=1 但是degree[5]=2 and degree[2]=3。我必须计算不相交集的总数。我一直在尝试使用以下结构：

但是因为它显示 p_data 数组非常大。所以请帮忙。我应该遵循什么样的数据结构或逻辑来计算上面定义的不相交集的总数。

我无法在这里发布图片：所以请参考这张图片： http: //postimage.org/image/sw2nrciib/

请有人说出可以执行的断续集的数量