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

阅读数:10 2019 年 11 月 9 日 15:59

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

(实现:加权 quick-union 算法)

幸好,我们只需简单地修改 quick-union 算法就能保证像这样的糟糕情况不再出现。与其在 union() 中随意将一棵树连接到另一棵树,我们现在会记录每一棵树的大小并总是将较小的树连接到较大的树上。这项改动需要添加一个数组和一些代码来记录树中的节点数,如算法 1.5 所示,但它能够大大改进算法的效率。我们将它称为加权 quick-union 算法(如图 1.5.7 所示)。该算法在处理 tinyUF.txt 时构造的森林如图 1.5.8 中左侧的图所示。即使对于这个较小的例子,该算法构造的树的高度也远远小于未加权的版本所构造的树的高度。

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

图 1.5.7 加权 quick-union

评论

发布