algorithm - 使用“路径减半”对不相交集进行 Find() 操作

Question

根据Disjoint-set_data_structure，在 Union 部分，我在理解路径减半方法的实现时遇到了问题。

 function Find(x)
   while x.parent ≠ x
     x.parent := x.parent.parent
     x := x.parent
   return x

我的第一次迭代看起来像这样：

第一次迭代后，x.parent指向x同一个节点（这不应该发生）。我需要有关此函数的正确流程和迭代的帮助

我对该函数的第 3 行和第 4 行以及“路径减半使路径上的每个其他节点都指向其祖父母”感到困惑。

任何帮助将不胜感激，谢谢！

score 1 · Accepted Answer

算法如下：从节点 x 开始，使 x 指向其祖父节点，然后移动到祖父节点本身，继续直到找到根节点，因为根节点的父节点就是根节点本身。

看一下图片，您实际上是通过将集合转换为二叉树来将集合减半（它不是正确的二叉树，但可以这样表示）。

假设我们有一个这样的集合：

8->7->6->5->4->3->2->1->0

其中箭头表示父级（例如8->7= 8 的父级是 7）

说我们打电话Find(8)

第一次迭代：

x = 8
8.parent = 7

8.parent = 8.parent.parent = 7.parent = 6
x = 8.parent = 7.parent = 6

第二次迭代：

x = 6
6.parent = 5

6.parent = 6.parent.parent = 5.parent = 4
x = 6.parent = 5.parent = 4

等等...

1 回答 1