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

Question

7

我正在尝试完成Cormen等人的算法导论中与不相交集数据结构有关的练习：

假设我们希望添加操作PRINT-SET（x），它接收一个节点x并以任意顺序打印x集合中的所有成员。展示如何仅向不相交集森林中的每个节点添加单个属性，以便PRINT-SET（x）需要时间线性地执行x集合的成员数量，并且其他操作的渐近运行时间不变。假设我们可以在O（1）时间内打印集合中的每个成员。

现在，我非常确定所需的属性是尾指针，因此它可以跟踪子级。

由于不相交集结构已经具有父属性，find-set（x）可以轻松地打印出向一个方向移动的节点。但是，现在拥有尾指针，让我们也可以沿另一个方向移动。

然而，我不确定如何编写此算法。如果有人能够用伪代码帮助我，那将不胜感激。

- user1596241

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Timothy Shields · Accepted Answer

每个节点应该有一个指向其所在集合中下一个节点的next指针。集合中的节点应该形成一个循环链表。

当创建单例集合时，节点的next指针指向自身。

当您将具有节点X和具有节点Y的集合合并（并且您已经通过将其规范化为集合代表来检查这些集合是否不同），您将合并循环链接列表，可以通过简单交换X.next和Y.next来实现；因此，这是一个O(1)操作。

要列出包含节点X的集合中的所有元素，请从X开始遍历循环链表。