3 algorithm time-complexity clrs disjoint-sets union-find
我试图在Cormen等人的算法导论中做这个练习,它与Disjoin Set数据结构有关:
假设我们希望添加操作
PRINT-SET(x),该操作被赋予一个节点x并x以任何顺序打印所有成员.展示我们如何在一个不相交的林中为每个节点添加一个单独的属性,这样就PRINT-SET(x)可以在所x设置的成员数量上花费时间线性,并且其他操作的渐近运行时间不变.假设我们可以在O(1)时间内打印该组的每个成员.
现在,我非常确定所需的属性是尾指针,因此它可以跟踪孩子.
由于不相交的集合结构已经具有父属性,因此find-set(x)可以轻松地打印出一个方向上的节点.但现在,有一个尾指针,让我们走向另一个方向.
但是,我不确定如何编写算法来执行此操作.如果有人能用伪代码帮助我,那将非常感激.
每个节点都应该有一个next指向它所在集合中下一个节点的指针.集合中的节点应该形成一个循环链表.
首次创建单例集时,节点的next指针指向自身.
当您合并设定节点X和节点与设定Y(和你已经检查了这些集是通过标准化来设定不同的代表),您只需交换合并循环链表,你可以做的X.next和Y.next; 所以这是一个O(1)操作.
要列出包含节点的集合中的所有元素,请X从X.开始遍历循环链接列表.