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

Question

我刚刚研究了不相交集合数据结构，知道它也被称为“并查数据结构”，并集和查找是该数据结构的两个主要操作。我们可以对不相交的集合进行并集，类似地我们可以进行查找操作；我想知道除了并集和查找之外，我们还可以对不相交集执行哪些其他操作。

Answer 1

不相交集合结构也称为“并查结构”。因此无论如何都应该支持 union、find 和 MakeSet 操作。其他操作并不是这个结构的全部内容，它们是否受支持取决于实现和您的目标。有时，您需要专门选择特定的实现来满足项目的附加操作需求。

除此之外，如果我们支持其他与集合相关的基本操作，那就太好了。让我们枚举它们：

• 两个集合的交集。由于集合是不相交的，因此除非这两个集合重合，否则它始终为空。
• 两组的联合——开箱即用支持。
• 从集合中获取元素 - 支持，它很可能是find 的结果。
• 从集合中删除元素——取决于实现。当集合被实现为森林时，这很棘手并且需要较慢的附加操作。当集合被实现为链表时，这很简单。
• 枚举集合，即迭代给定集合中的每个元素。这又取决于实现：对于链表来说很简单，对于类似森林的实现则需要额外的结构来支持。

Answer 2

使用普通的联合查找数据结构，您无法枚举实际的集合，因此许多集合操作不可用。这是因为在普通版本中只有一个方向的指针 --- 在下图中，每条对角线对应一个向上的箭头，根（顶线）是集合的根对象：

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

所以没有找到集合 1 的所有对象的方法；例如，您无法从根节点跟踪到它们的路径。您也可以使用向下的指针，但这会使数据结构变得非常复杂，因为一个对象在数据结构中可以有任意数量的父对象。

所以它实际上主要用于以下操作：

• 回答：我的对象 A 和 B 是否属于同一集合？
• 合并集合 S1 和 S2，以便集合中的所有对象现在被认为属于同一集合。

为了详细说明这一点，并集数据结构对于它支持的操作具有非常低的时间复杂度；合并集合和回答相同集合的查询都需要摊余常数时间 (O(1))；由于时间复杂性，您无法支持所有集合操作。例如，标准集合表示是通过[二叉]搜索树，其中大多数操作至少具有 O(log n) 复杂度。

Answer 3

正如您的问题和其他受访者似乎暗示的那样，并查不相交集合结构的要点并不在于执行基本集合运算。相反，它是某些算法所需结构的高效实现。特别是，查找连通分量和最小生成树在并查找不相交集的基础上构建了最有效的实现。