可以对不相交集合执行哪些操作？

Question

我刚刚研究了不相交集数据结构，并且我知道它也被称为“union-find数据结构”，union和find是这个数据结构的两个主要操作。我们可以在不相交集合上执行联合，类似的，我们可以执行查找操作;我想知道除了union和find以外，我们可以在不相交的集合上执行哪些其他操作。

Answer 1

独立集合结构也被称为“合并 - 查找结构”。因此无论如何union,find和MakeSet操作应该得到支持。其他行动不是这个结构的全部，它们是否得到支持取决于实施和目标。有时候您需要专门选择特定的实施方式，以满足您项目对额外操作的需求。

除此之外，如果我们支持的其他基本的设置相关的操作这将是很好。让我们列举一下：

• 十字路口两套。由于集合是不相交的，除非这两个集合重合，否则它总是空的。
• 工会的两套 - 支持开箱即用。
• 从集合获取元素 - 的支持，这是最有可能的find结果。
• 从集合删除元素 - 取决于执行。当集合被实现为森林时，它很棘手并且需要较慢的附加操作。当集合被实现为链表时，它很简单。
• 枚举设定，即迭代在该给定组中的每个元件。这个依赖于实现：链接列表很简单，对于像森林一样的实现，它需要额外的结构来支持。

Answer 2

使用vanilla union-find数据结构，您无法枚举实际集合，因此许多集合操作都不可用。这是因为在香草版本中，只有指向一个方向的指针---在下图中，每条对角线对应于向上的箭头，并且根（顶部线）是集合的根对象：

 o [set1]   o [Set2] 
    /\    \ 
    o o    o 
/
o 

所以没有办法找到所有的对象，比如set 1;例如，您不能从根节点追踪到它们的路径。您也可以向下指针，但这会显着地使数据结构复杂化，因为对象在数据结构中可以有任意数量的父项。

所以它实际上多为以下操作：

• 答到：做我的对象A和B属于同一组或没有？
• 合并设置S1和S2，以便在集合中的所有对象现在都被认为属于同一组

为了详细说明这一点，工会组数据结构有它支持的操作非常低的时间复杂度;合并集合和回答相同集合查询采取分摊的恒定时间（O（1））;由于这种非常复杂的时间，你不能支持所有的设置操作。例如，一个标准集表示是由一个[二进制]搜索树，其中大多数操作至少具有O（log n）复杂性。

Answer 3

联合发现不相交集合结构的关键不在于执行基本集合操作，因为您的问题和其他受访者似乎暗示。相反，它是关于某些算法需要的结构的高效实现。特别是，找到连接组件和最小生成树将在联合查找不相交集之上构建其最有效的实现。