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

Question

我正在尝试在 Cormen 等人的算法简介中做这个练习，这与 Disjoin Set 数据结构有关：

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

现在，我很确定需要的属性是一个尾指针，所以它可以跟踪孩子。

由于不相交的集合结构已经有一个父属性，find-set(x)可以很容易地打印出一个方向的节点。但是现在，有了一个尾指针，让我们也转向另一个方向。

但是，我不确定如何编写算法来做到这一点。如果有人可以用伪代码帮助我，那将不胜感激。

Answer 1

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

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

当您将集合与节点合并并与节点X集合时Y（并且您已经通过规范化集合代表检查了这些集合是否不同），您可以合并循环链表，您可以通过简单地交换X.next和来完成Y.next；所以这是一个O(1)操作。

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