在线性时间内打印出不相交的数据结构中的节点 [英] Printing out nodes in a disjoint-set data structure in linear time

问题描述

我正试图在Cormen等人的算法简介"中进行此练习，该练习与Disjoin Set数据结构有关:

I'm trying to do this exercise in Introduction to Algorithms by Cormen et al that has to do with the Disjoin Set data structure:

假设我们希望添加操作PRINT-SET(x)，该操作已给出 节点x，并以任何顺序打印x的集合的所有成员.展示如何 我们可以向不交集中的每个节点仅添加一个属性 森林，以便PRINT-SET(x)花费个时间线性的成员数 x的设置以及其他运算的渐近运行时间 不变.假设我们可以在O(1)中打印集合的每个成员 时间.

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. Assume that we can print each member of the set in O(1) time.

现在，我非常确定所需的属性是 tail指针，以便它可以跟踪子项.

Now, I'm quite sure that the attribute needed is a tail pointer, so it can keep track of the children.

由于不相交集结构已经具有父属性，因此find-set(x)可以轻松打印出沿一个方向行进的节点.但是现在，有了尾巴指针，我们也要往另一个方向前进.

Since the disjoint set structure already has a parent attribute, find-set(x) can easily print out nodes going in one direction. But now, having a tail pointer, let's us go the other direction as well.

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

However, I'm not sure how I would write the algorithm to do this. If anyone could help me out in pseudocode, that would be much appreciated.

推荐答案

每个节点应具有指向其所在集合中下一个节点的next指针.集合中的节点应形成圆形链接列表.

Each node should have a next pointer to the next node in the set it is in. The nodes in a set should form a circular linked list.

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

When a singleton set is first created, the node's next pointer points to itself.

当您将集合与节点X合并并与节点Y进行合并(并且已经通过归一化集合代表检查了这些集合是否不同)时，您将合并循环链接列表，您可以通过以下方式进行合并:只需交换X.next和Y.next；所以这是O(1)操作.

When you merge set with node X and set with node Y (and you've already checked that those sets are different by normalizing to set representatives), you merge the circular linked lists, which you can do by simply swapping X.next and Y.next; so this is a O(1) operation.

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

To list all the elements in the set containing node X, traverse the circular linked list starting from X.

这篇关于在线性时间内打印出不相交的数据结构中的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！