5

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

4

3 回答 3

3

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

除此之外，如果我们支持其他基本的集合相关操作会很好。让我们列举它们：

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

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

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

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

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

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

为了详细说明这一点，联合集数据结构对其支持的操作具有非常低的时间复杂度；合并集合和回答同一个集合的查询都需要摊销常数时间（O（1））；由于这种时间复杂度，你不能支持所有的集合操作。例如，标准集表示是由 [二进制] 搜索树，其中大多数操作至少具有 O(log n) 复杂度。

于 2010-02-13T18:11:23.480 回答
0

The point of the union-find disjoint set structure is not so much about performing elementary set operations, as your question and other respondents seem to be suggesting. Instead, it's about being a highly efficient implementation of the structure that certain algorithms need. In particular, finding connected components and minimum spanning trees build their most efficient implementations on top of union-find disjoint sets.

于 2010-02-13T19:23:23.707 回答