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

Question

刚刚研究了disjoint set数据结构，我知道它也叫“联合查找数据结构”，联合和查找是这个数据结构的两个主要操作。我们可以对不相交的集合进行并集，同样我们可以进行查找操作；我想知道除了 union 和 find 之外，我们还可以对不相交的集合执行哪些其他操作。

Answer 1

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

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

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