算法(4th ed)(207):基础——案例研究:union-find 算法 7.2.4

阅读数:6 2019 年 11 月 9 日 15:52

算法(4th ed)(207):基础——案例研究:union-find 算法 7.2.4

(实现:森林的表示)

quick-union 算法的代码很简洁,但有些难以理解。用节点(带标签的圆圈)表示触点,用从一个节点到另一个节点的箭头表示链接,由此得到数据结构的图像表示使我们理解算法的操作变得相对容易。我们的得到的结构是——从技术上来说,id[] 数组用父链接的形式表示了一片森林。为了简化图表,我们常常会省略链接的箭头(因为它们的指向全部朝上)和树的根节点中指向自己的链接。tinyUF.txt 的id[] 数组所对应的森林如图 1.5.5 所示。无论我们从任何触点所对应的节点开始跟随链接,最终都将达到含有该节点的树的根节点。可以用归纳法证明这个性质的正确性:在数组被初始化之后,每个节点的链接都指向它自己;如果在某次union() 操作之前这条性质成立,那么操作之后它必然也成立。因此,quick-union 中的find() 方法能够返回根节点所对应的触点的名称(这样connected() 才能够判定两个触点是否在同一棵树中)。这种表示方法对于这个问题很实用,因为当且仅当两个触点存在于相同的分量之中时它们对应的节点才会在同一棵树中。另外,构造树并不困难:quick-union 中union() 的实现只用了一条语句就将一个根节点变为另一个根节点的父节点,从而归并了两棵树。

算法(4th ed)(207):基础——案例研究:union-find 算法 7.2.4

图 1.5.5 quick-union 算法的轨迹(以及相应的森林)

评论

发布