algorithm - Union-Find:有效地检索集合的所有成员

Question

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

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

直到现在，我天真地测试了 E 的所有元素对集合 S 的成员资格。但是昨天我正在阅读“Introduction to Algorithms”(CLRS，第 3 版，ex. 21.3-4)，并且在练习中，我发现:

Suppose that we wish to add the operation PRINT-SET(x), which is given a node x and prints all the members of x's set, in any order. Show how we can add just a single attribute to each node in a disjoint-set forest so that PRINT-SET(x) takes time linear in the number of members of x's set, and the asymptotic running times of the other operations are unchanged.

“与 x 集合的成员数量呈线性关系”将对我的问题有很大改进!所以，我正在尝试解决这个问题……在尝试了一些不成功之后，我在 Stack Overflow 上寻求帮助!

Answer 1

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

我是在他的帮助下做的

Printing out nodes in a disjoint-set data structure in linear time.

我在第一篇文章后发现了这个话题，我很抱歉。

在伪代码中(尚未测试):

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)