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

阅读数:8 2019 年 11 月 9 日 15:51

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

(实现:quick-union 算法)

我们要讨论的下一个算法的重点是提高 union() 方法的速度,它和 quick-find 算法是互补的。它也基于相同的数据结构——以触点作为索引的 id[] 数组,但我们赋予这些值的意义不同,我们需要用它们来定义更加复杂的结构。确切地说,每个触点所对应的 id[] 元素都是同一个分量中的另一个触点的名称(也可能是它自己)——我们将这种联系称为链接。在实现 find() 方法时,我们从给定的触点开始,由它的链接得到另一个触点,再由这个触点的链接到达第三个触点,如此继续跟随着链接直到到达一个根触点,即链接指向自己的触点(你将会看到,这样一个触点必然存在)。当且仅当分别由两个触点开始的这个过程到达了同一个根触点时它们存在于同一个连通分量之中。为了保证这个过程的有效性,我们需要union(p, q) 来保证这一点。它的实现很简单:我们由 p 和 q 的链接分别找到它们的根触点,然后只需将一个根触点链接到另一个即可将一个分量重命名为另一个分量,因此这个算法叫做 quick-union。和刚才一样,无论是重命名含有 p 的分量还是重命名含有 q 的分量都可以,右侧的这段实现重命名了 p 所在的分量。图 1.5.5 显示了 quick-union 算法在处理 tinyUF.txt 时的轨迹。图 1.5.4 能够很好地说明图 1.5.5(见 1.5.2.4 节)中的轨迹,我们接下来要讨论的就是它。

复制代码
private int find(int p)
{ // 找出分量的名称
while (p != id[p]) p = id[p];
return p;
}
public void union(int p, int q)
{ // 将 p 和 q 的根节点统一
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) return;
id[pRoot] = qRoot;
count--;
}
quick-union

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

图 1.5.4 quick-union 算法概述

评论

发布