algorithm - 使用“路径减半”对不相交集进行 Find() 操作
问题描述
根据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 行以及“路径减半使路径上的每个其他节点都指向其祖父母”感到困惑。
任何帮助将不胜感激,谢谢!
解决方案
算法如下:从节点 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
等等...
推荐阅读
- javascript - FullCalendar eventDrop 在几天之间不起作用
- java - NetBeans 找不到包 java.lang
- java - 为什么这个 java.lang.NullPointerException 错误?
- react-native - 反应原生导航显示白屏
- html - Chrome DevTools 中的响应式模拟是否总是准确的?
- c# - 如何找到作为 datagridview 指定行和列的一部分的单元格的值?
- string - 哈希中键的 Perl 计数频率
- c++ - 将对象分配给数组 C++
- graphql - gatsby-source-contentful 不适用于 gatsby-transformer-remark
- php - 尝试制作一个用户配置文件