问题标签 [union-find]

如果这个问题有点宽泛，我深表歉意，但我很难理解如何创建最小成本生成树。如果重要的话，这是在 C++ 中。

据我了解，您将使用 Kruskal 来选择构建生成树的最小成本边。我的想法是将边缘读入一个minheap，这样你就可以从顶部移除，以便以最低的成本获得边缘。

到目前为止，我只能为 union-find 实现 minheap 和 sets，我仍然不确定 union-find 的目的和用于创建生成树的排序算法。

我将不胜感激任何建议。

编辑：我不限于联合查找、minheap、kruskals 和排序算法，也不需要我做任何事情。这些只是导师建议的项目。

我正在阅读著名的union-find 问题，这本书说：“find 或 union 都需要O(n)时间，而另一个需要O(1)....”

但是使用位串来表示集合呢？然后联合（使用位或）和查找（遍历集合列表检查相应的位是1）都将采用O(1)..

这个逻辑有什么问题？

对于许多问题，我认为推荐的解决方案是使用联合查找数据结构。我试图阅读它并思考它是如何实现的（使用 C++）。我目前的理解是，它只是一个集合列表。所以要找到一个元素属于哪个集合，我们需要n*log n操作。而当我们必须执行并集时，我们必须找到需要合并的两个集合并对其进行操作set_union。这对我来说看起来不是很有效。我对这个数据结构的理解是正确的还是我遗漏了什么？

在连接组件标签中，如果我看到左侧的像素和当前像素上方的像素具有相同的颜色但标签不同，我不能自动将它们的标签重新分配为相同的（而不是使用等价表） ?

Wikipedia和MathWorks将最小标签分配给当前像素，否则将保持相邻像素相同。然后，他们用另一遍擦亮标签表。除非我弄错了，否则我的调整将允许我在一次通过中统一标记图像。有没有我的小调整会破坏算法的例子？

我无法将快速查找算法中的联合操作与集合论中 AUB 的一般含义相关联。

书（C++ 中的算法 Robert Sedgewick）告诉联合操作是“扫描每个输入对的整个数组。（代码中的第 9 行和第 10 行）。

基本上，我们将节点 q 的值复制到与节点 p 具有相同值的所有其他节点。为什么我们将这个操作命名为 UNION？

代码直接从书中复制。

我注意到Data.UnionFind使用 IO monad 通过 IORefs 提供指针。我想每个人在以纯代码在本地使用它时都会愉快地调用unsafePerformIO它，因为数据结构很好理解，但是..

这种数据结构是否有规范的清洁方法？也许是 IO 的包装器，它通过禁止大多数 IO 操作使不可避免unsafePerformIO的不安全“看起来”变得不那么安全？

有一个“带路径压缩的加权快速联合”算法。

编码：

问题：

1. 路径压缩如何工作？id[i] = id[id[i]]意味着我们只到达节点的第二个祖先，而不是根。

2. iz[]包含从0到 的整数N-1。如何iz[]帮助我们知道集合中的元素数量？

有人可以为我澄清一下吗？

我有一条记录，将图形描述为一组节点和边：

由于我永远不会删除边，我想使用联合查找结构（添加边时可以轻松更新）来跟踪连接的组件，因为我想映射连接的组件，所以它会很有用也将它们作为一组集合。当然，我想获得一个节点的组件。

我找到了等价库，之所以选择它是因为我看不到如何使用union-find创建集合，而持久等价需要知道值范围。

现在我可以创建关系，并使用以下方法返回集合集：

但是：使用fromList非常幼稚，应该可以直接从内部数据结构中获取所有等价类。

而且，更重要的是：如何将等价关系存储在我的数据结构中？

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

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

我正在为联合/查找结构实现快速联合算法。在“Java 中的算法”图书站点给出的实现中，普林斯顿实现在实现路径压缩（在find()方法中）时未能保持树的大小不变。这不应该对算法产生不利影响吗？还是我错过了什么？另外，如果我是对的，我们将如何修改大小数组？