问题标签 [union-find]

这是我对不相交集的 Objective-C 实现。- 正数指向父母。- 负数表示根数和子数。（所以它们每个都从 -1 开始脱节。） - 索引充当我正在分组的数据。似乎工作正常......只是有几个问题。

1. find：如何压缩路径？因为我不是递归地做，我是否必须存储路径并在找到根目录后再次循环设置？

2. 加入：我是基于儿童数量而不是深度加入！？我想这是不对的。如果深度相等，我是否需要在加入期间做一些特别的事情？

谢谢。

不相交集.h

不相交集.m

我一直在使用 coursera 上的课程研究算法。在第一堂课中，正在讨论快速联合加权。我明白了它的作用，我已经使用他们的代码对其进行了测试，并为它编写了一个小测试。

一切都很清楚，只有一点：当您创建两个对象的并集时，它会将具有最小树的对象添加到较大的对象中。同时，较大树的大小将随着较小树的大小在一个单独的数组中递增，该数组用于确定哪棵树更大。由于数组以每个索引的值 1 启动（每个节点本身基本上是 1 个对象的树），为什么该索引的值不设置为 0 而不是保持为 1？

为了说明这一点：

为什么合并索引的大小是 1 而不是 0？您可以在此处找到对其进行测试的代码。请注意，实现与讲师提供的示例相同，这就是为什么我假设我的代码是正确的。

对于自动机算法，我需要使用函数式语言的快速 Union-Find 数据结构。由于我需要正式证明数据结构的正确性，所以我更喜欢简单的结构。

我想要做的是计算一个集合中元素的等价S类R ⊆ S × S。最后我想得到的是一些函数f: S → S，它将任何元素映射S到其R-equivalence 类的（规范）代表。通过“规范”，我的意思是我不在乎它是哪个代表，只要它对于一个等价类的所有元素都是相同的，即我想f x = f y ⟺ (x,y) ∈ R持有。

函数式语言中最好的数据结构和算法是什么？我应该补充一点，我真的需要“正常”功能代码，即没有可变性/状态转换器单子。

编辑：与此同时，我想出了这个算法：

这将创建一个映射，将 的任何元素映射S到其等价类的代表，其中代表是迭代到达的第一个元素S。我认为这实际上具有线性时间（如果地图操作是恒定的）。但是，我仍然对其他解决方案感兴趣，因为我不知道这在实践中的效率如何。

（我的关系在内部表示为“S → (S Set) option”，因此在 {t | (s,t) ∈ R} 上的迭代 - 这是对该结构的廉价操作。）

我只std::vector在这个问题中使用，我可以保证每个向量中没有重复（但每个向量中没有任何顺序）。如何合并我拥有的向量？

例子：

如果我有以下向量...

在联合之后，我应该只剩下两个向量：

同样，我只使用矢量，std::set不允许。

我只在这个问题中使用 std::vector 并且每个向量都是有序的，没有重复。现在我想合并具有相同数字的向量。所以 2 3 可以与 3 4 5 联合，但不能与 4 5 或 1 5 联合。

例子：

如果我有以下向量...

联合之后，我应该只剩下 2 个向量：

代码：

我尝试使用 set_union 和 set_intersection 来实现我的目标，但它没有按预期工作。我怀疑问题出在我没有正确更改的向量大小上。请帮忙。谢谢！

编辑：

这是错误的代码，最初我对联合有问题，但现在它会自动运行..现在我想我主要不确定如何使用 set_intersection 来找出是否有交集

我有一个 N*N 布尔对称矩阵来显示每个元素的关系。

例如矩阵

表示元素 1 与 1、3 有关系；元素 2 与 2,3 等有关系。

现在我想对元素进行聚类，因为矩阵大小很大（N=9000），我不想使用三层循环，而是想使用联合查找算法。

对于执行代码：

问题是，我想始终使用最小的索引作为集群标签，但有时我的代码没有使用正确的标签。

例如，元素 2、3、100 是相关的。我希望集群有标签 2，但我得到标签 100 的结果。谁能告诉我我的逻辑错误？

我不确定是否

工作，因为我担心如果，例如，{1,2,3}->label 1 ;{4,6}->label 4 当我调用 union(3,4) 时，labels[6] 也会是修改为1？

在尝试推出自己的优化之前，我正在寻找 Scala 中联合查找或不相交集数据结构的现有实现，因为优化看起来有些复杂。

我的意思是这种事情 - 两个操作union和find优化。

有人知道现有的东西吗？我显然试过用谷歌搜索。

我正在阅读一本关于算法的书（“C++ 中的数据结构和算法”）并且遇到了以下练习：

前任。20. 修改cycleDetectionDFS()，以便它可以确定特定边是否是无向图中循环的一部分。

在关于图表的章节中，书中写道：

让我们回顾一下前面的部分，深度优先搜索保证生成一棵生成树，其中没有edges 使用的元素depthFirstSearch()导致与其他元素的循环edges。这是因为如果顶点v和u属于edges，那么边（vu）会被 忽略depthFirstSearch()。修改时会出现问题，depthFirstSearch()以便它可以检测特定边（vu）是否是循环的一部分（参见练习 20）。如果将这种修改后的深度优先搜索分别应用于每条边，那么总运行将是 O(E(E+V))，对于密集图，这可能变成 O(V^4)。因此，需要找到更好的方法。

任务是确定两个顶点是否在同一个集合中。实现此任务需要两个操作：找到顶点 v 所属的集合，如果顶点v属于其中一个集合，而w属于另一个集合，则将两个集合合并为一个集合。这被称为并集问题。

稍后，作者描述了如何将两个集合合并为一个，以防传递给函数的边union(edge e)连接不同集合中的顶点。

但是，我仍然不知道如何快速检查边缘是否是循环的一部分。有人可以给我一个与上述联合查找问题相关的算法的粗略解释吗？

我来自命令式背景，正在尝试实现一个简单的不相交集（“union-find”）数据结构，以练习在 Haskell 中创建和修改（持久）数据结构。目标是有一个简单的实现，但我也关心效率，我的问题与此有关。

首先，我创建了一个不相交集的森林实现，并使用按等级联合，并从定义“点”的数据类型开始：

脱节集森林是一个IntMap带有Int → Point映射的：

单例集只是从其值x到值为x的 Point的映射，没有父级且等级为 1：

现在，有趣的部分—— union。此操作将通过将另一个点设置为其父点来修改一个点（并在某些情况下更改其等级）。在Points 等级不同的情况下，Point简单地“更新”（创建一个新点）以使其父点指向另一个。在它们相等的情况下，Point创建一个新的，其等级增加一：

现在，对于我真正的问题，如果在这种EQ情况下我做了以下事情：

即首先插入一个新的Point x并增加其等级，然后让y'' 的父级成为一个新的Point x并增加其等级，这是否意味着它们不再指向Point内存中的相同？（这有关系吗？在使用/创建持久数据结构时我应该担心这些事情吗？）

为了完整起见，这里是findSet：

（也欢迎对这段代码的效率和设计发表一般评论。）

我正在实施不相交集数据结构来进行联合查找。我在 Wikipedia 中看到了以下声明：

...每当相同等级 r 的两棵树联合起来时，结果的等级为 r+1。

当树的等级相同时，为什么连接树的等级只增加一？如果我简单地添加两个等级（即2*r）会发生什么？