打印出不相交的节点集合以线性时间 [英] Printing out nodes in Disjoint Set in linear time

问题描述

我想通过Cormen等，有做的设置不交数据结构做这个练习算法导论：

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的组的所有成员，以任何顺序。说明如何   我们可以在不相交集只添加一个属性到每个节点   森林使打印-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.

现在，我很肯定所需要的属性是一个尾指针，因此它可以跟踪孩子。由于不相交集结构已经有一个父属性，找到设置（X），即可轻松打印出的节点会在一个方向上。但现在，有一个尾指针，让我们一起去另一个方向为好。 但是，我不知道我怎么尔德写算法来做到这一点。如果任何人都可以hekp我在伪code，那将是多AP preciated。

Now, I'm quite sure that the attribute needed is a tail pointer so it can keep track for children. 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 wold write the algorithm to do this. If anyone could hekp me out in pseudocode, that would be much appreciated.

推荐答案

每个节点应该有一个接下来指针的设置是在未来的节点，节点一组应该形成一个循环链表。

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.

当第一次创建一个单集，该节点的接下来指针指向自己。

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

当您合并设置节点 X 键，设置节点是（和你已经检查了这些集正常化设置重新presentatives），您合并循环链表，这是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 is O(1).

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

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

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