8

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

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

直到现在，我天真地测试E了 set的所有元素的成员资格S。但是昨天我正在阅读“算法简介”（CLRS，第 3 版，ex. 21.3-4），并且在练习中，我发现：

假设我们希望添加操作PRINT-SET(x)，给定一个节点并以任意顺序x打印 集合的所有成员。x展示我们如何向不相交集森林中的每个节点添加一个属性，从而使PRINT-SET(x)时间与x的集合成员数成线性关系，并且其他操作的渐近运行时间保持不变。

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

4

2 回答 2

5

我设法在不使用列表的情况下编写了另一种算法（使用我的编程语言，即 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)
于 2014-04-14T13:32:47.343 回答
4

回想一下，union-find 是作为倒置树实现的，其中对于每个集合 S = {v 1 , v 2 , ..., v n }，您有 v n - 1条边，它们最终具有相同的根（或水槽）。

现在，每当您向这棵树添加一条边 (v i , v j ) 时，添加另一条边（使用新属性） (v j , v i )。当你删除一个节点时，也要删除该属性。

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

请注意，该属性实际上是一个节点列表，但所有列表组合的元素总数仍然是n - 1。

这会给你第二棵树，但不会倒过来。现在，使用根，并进行一些树遍历（使用例如BFS或DFS），您可以打印所有元素。

于 2014-04-14T08:27:48.583 回答