联合查找:有效地检索集合的所有成员

Question

我正在使用union-find算法。在我的程序的第一部分中，该算法计算一个大集合E的分区。

之后，我想检索集合S的所有成员，该集合包含一个给定的节点x。

直到现在，我还天真地测试E的所有元素对集合S的成员关系。但昨天我在读《算法导论》（CLRS，第3版，前21.3-4），在练习中，我发现：

假设我们希望添加操作PRINT-SET(x)给定节点x并按任何顺序打印x集合的所有成员。展示如何在使得PRINT-SET(x)在x集合的成员数，以及其他操作不变。

"x集合的成员数是线性的"对于我的问题将是一个很大的改进！所以，我正在努力解决这个难题。。。在尝试了几次失败之后，我请求有关Stack Overflow的帮助！

Answer 1

我设法在不使用列表的情况下编写了另一种算法（与我的编程语言，即ANSI-C一起使用更方便）。

我在的帮助下做到了

在线性时间内打印出不相交的集合数据结构中的节点。

我在第一篇帖子后发现了这个帖子，我很抱歉。

在伪代码中（尚未测试）：

MAKE-SET(x)
    x.p = x
    x.rank = 0
    x.link = x        # Circular linked list
UNION(x,y)
    sx = FIND-SET(x)
    sy = FIND-SET(y)
    if sx != sy
        LINK(sx, sy)
LINK(x,y)
    temp = y.link     # Concatenation
    y.link = x.link   # of the two
    x.link = temp     # circular lists
    if x.rank > y.rank
        y.p = x
    else x.p = y
         if x.rank == y.rank
             y.rank = y.rank + 1
FIND-SET(x)
    if x != x.p
        x.p = FIND-SET(x.p)
    return x.p
PRINT-SET(x)
    root = x
    PRINT(x)
    while x.link != root
        x = x.link
        PRINT(x)

Answer 2

回想一下，并集查找是作为倒置树实现的，其中对于每个集合S={v₁、v₂，…，v_n｝，您有v_n-1边，它们最终具有相同的根（或sink）。

现在，无论何时向该树添加边（v_i，v_j），都要添加另一条边（使用新属性）（v_j

请注意，新的边与旧的边是分开的。打印集合中的所有元素时，只能使用。并在原始算法中修改任何原始边时对其进行修改。

注意，这个属性实际上是一个节点列表，但所有列表中的元素总数加起来仍然是n-1。

这将为您提供第二个树，但不是倒置。现在，使用根，并进行一些树遍历（例如使用BFS或DFS），您可以打印所有元素。