问题标签 [disjoint-sets]

http://en.wikipedia.org/wiki/Disjoint_sets

http://en.wikipedia.org/wiki/Kruskal's_algorithm

用于不相交集的联合/查找数据结构...

I am trying to implement Disjoint Sets for use in Kruskal's algorithm, but I am having trouble understanding exactly how it should be done and in particular, how to manage the forest of trees. After reading the Wikipedia description of Disjoint Sets and after reading the description in Introduction to Algorithms (Cormen et al) I have come up with the following:

I am pretty sure this is incomplete though and that I am missing something.

Introduction to Algorithms mentions that there should be a forest of trees, but it does not give any explanation for a practical implementation of this forest. I watched CS 61B Lecture 31: Disjoint Sets ( http://www.youtube.com/watch?v=wSPAjGfDl7Q ) and here the lecturer uses only an array to store both the forest and all its trees and values. There is no explicit 'Node' type of class as I have, mentioned. I have also found many other sources (I cannot post more than one link), which also use this technique. I would be happy to do this, except that this relies on the indices of the array for lookup and since I want to store values of type other than int, I need to use something else (std::map comes to mind).

Another issue that I am unsure about is memory allocation because I am using C++. I am storing trees of pointers and my MakeSet operation will be: new DisjointSet::Node; . Now, these Nodes only have pointers to their parents, so I'm not sure how to find the bottom of a tree. How will I be able to traverse my trees to deallocate them all?

I understand the basic concept of this data structure, but I'm just a bit confused about the implementation. Any advice and suggestions would be most welcome, thank you.

到目前为止，我所拥有的主要基于 Cormen 等人的“算法简介”的第 571 页。

我在 python 中有一个 Node 类，它代表一个集合：

这个实现将使用一个List节点作为森林（我愿意接受更好的方法来存储集合）。

Initialize()返回一个节点列表，我将其存储在变量中set并传递给其他函数。

Find在森林中搜索值并返回它出现的集合。我选择使用for s in range(len(set)):，以便在递归中我可以缩小传递的集合列表set[s:]。

Merge通过找到它们并提升排名较高的集合来合并森林中的集合。

我在执行Finds 和Merges 时遇到了一些错误，即Find没有返回正确的集合，所以我不确定是否Merge也能正常工作。我会很感激一些帮助，以确保正确实施这些功能。

有一个关于今天到期的作业的问题已经发布了解决方案，我不明白正确的答案。该问题以不相交集合森林的形式处理不相交集合的最佳情况性能，该森林利用加权联合算法来提高性能（较小的树的根作为子节点连接到两棵树中较大的树的根) 但不使用路径压缩算法。

问题是在 n 个单例节点上执行 (n-1) 联合操作和 m>=n 以任何顺序查找操作的最佳情况是否是 Omega(m*logn) 解决方案确认是正确的，如下所示：

有一个由 n-1 个联合组成的序列 S，后跟 m >= n 的查找需要 Omega(m log n) 时间。序列 S 以序列 n-1 Unions 开始，该序列构建一棵深度为 Omega(log n) 的树。然后它有 m>=n 查找，每个查找该树的最深叶子，因此每个查找都需要 (log n) 时间。

我的问题是，为什么这证明下限是 Omega(m*logn) 是正确的？这不只是一个孤立的例子，当界限是 Omega(m*logn) 时，它不能证明所有输入的情况？我确信在反驳一个主张时只需要展示一个反例，但需要为所有可能的输入证明一个谓词以证明其正确性。

在我的回答中，我指出了这样一个事实，即当您开始将两个单例节点连接在一起时，您可能会有一个案例。然后，您将另一个单例加入到该 2 节点树中，其中 3 个节点共享同一个父节点，然后是另一个节点，等等，直到您将所有 n 个节点连接在一起。然后，您有一个树，其中 n-1 个节点都指向同一个父节点，这本质上是您使用路径压缩获得的结果。然后每个 FIND 在 O(1) 时间内执行。因此，一系列 (n-1) 个并集和 m>=n 发现最终成为 Omega(n-1+m) = Omega(n+m) = Omega(m)。

这是否意味着 Omega(m*logn) 界限不严格，因此主张不正确？我开始怀疑我是否不完全了解 Big-O/Omega/Theta：/

编辑：将问题解决得更清楚一点

EDIT2：这是原始问题的呈现方式和解决方案（我花了一点时间才意识到甘巴里诺和其他人完全编造了；铁杆意大利教授）

根据维基百科，我使用不相交集数据结构在 C++ 中实现了 Kruskal 算法，如下所示：

我的问题是：我需要这两行代码吗？如果是这样，它们的重要性是什么？

1. int px=findset(x),py=findset(y); 在合并而不是int px=parent[x],py=parent[y];
2. parent[x]=findset(parent[x]);在 findset 而不是return findset(parent[x]);

有3个线程。它们中的每一个都使用自己的一组字典键工作（读取、写入）。所以键对于不同的线程是互斥的。还有多个线程只读取数据。

这两种方法中哪一种在速度方面更有效：

1. 创建单个字典（ConcurrentDictionary 类型）
2. 为这 3 个线程中的每一个创建一个单独的字典（ConcurrentDictionary 类型）。

乍一看，第二种方法更有效，因为没有作家争用。这里有什么陷阱吗？如果两种方法之间的差异微不足道，那么我将采用第一种方法。

我认为我的析构函数现在很好......但仍然不确定如何从 operator() 重载中调用 print_set 。

它按应有的方式输出，但我觉得有一种简单的方法可以从函数调用重载中调用 print_set ......似乎无法得到我想要的东西......

头文件：

执行：

司机：

我有一个字典，其中包含 id 和每个 ID 的多个值，它们是字符串。对于每个 Id 中的每个值，我进行数据库查询并获得设置结果：

所以对于每个值，假设运行我执行一个查询，它返回另一组数据，然后选择该组的每个值并运行查询，这将给出另一组，最后我到了只有一个项目得到返回的地步。一旦我完成了每个子元素的最后一个元素，Run我就会移动Jump并继续。

我之前问过这个问题，但没有得到任何结果，所以人们告诉我删除代码并再次问这个问题。这是我几天前问的同一问题的链接。我需要实现类似 disjoin set 的东西吗？

我在连接组件标签中使用不相交集时遇到了一些困难。我看过很多例子，也看过这个问题，博天提供了一个非常好的不相交集实现作为 C++ 链表。我已经在我的程序中实现了连接组件标签（标签是简单的整数），但是我很难解决具有不相交集的标签之间的等价性。

任何人都可以帮助我 - 也许使用 Bo Tian 的实现？我认为这也将帮助其他人达到这一点。

编辑

我的算法遍历图像，当它找到两个标签时，两个连接的像素具有不同的标签，它必须在“等价注册表”（这将是不相交集森林）中做一个注释。在循环整个图像之后，我必须通过（对图像进行第二次遍历）查看注册表，然后将这些像素标记为集合中的最小等效标签来解决等价问题。

我有三个语法：

A -> aB | 乙 | CBB

B -> aB | 巴 | aBB

C->aaA | 乙 | 出租车

我需要“通过执行成对不相交测试来确定 [它们] 是否是 LL 语法，显示每个非终结符的每个 RHS 的第一组。

这是我目前所拥有的......

A -> aB | 乙 | CBB

第一(aB) = a

第一（b）= b

第一(CBB) = aaA = a

这是我遇到的麻烦。我正确地做 CBB 了吗？如果是这样，我会说它们相交并且规则未通过测试。（对？）

B -> aB | 巴 | aBB

第一(aB) = a

第一（ba）= b

第一(aBb) = a

它们相交，因此该规则未通过测试。

C->aaA | 乙 | 出租车

第一（aaA）=一个

第一（b）= b

第一(caB) = c

它们不相交，因此规则通过