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

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

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

(实现:quick-find 算法)

一种方法是保证当且仅当 id[p] 等于 id[q]pq 是连通的。换句话说,在同一个连通分量中的所有触点在 id[] 中的值必须全部相同。这意味着 connected(p, q) 只需要判断 id[p] == id[q],当且仅当pq 在同一连通分量中该语句才会返回true。为了调用union(p, q) 确保这一点,我们首先要检查它们是否已经存在于同一个连通分量之中。如果是我们就不需要采取任何行动,否则我们面对的情况就是 p 所在的连通分量中的所有触点的id[] 值均为同一个值,而 q 所在的连通分量中的所有触点的 id[] 值均为另一个值。要将两个分量合二为一,我们必须将两个集合中所有触点所对应的id[] 元素变为同一个值,如表 1.5.2 所示。为此,我们需要遍历整个数组,将所有和 id[p] 相等的元素的值变为 id[q] 的值。我们也可以将所有和 id[q] 相等的元素的值变为 id[p] 的值——两者皆可。根据上述文字得到的find()union() 的代码简单明了,如下面的代码框所示。图 1.5.3 显示的是我们的开发用例在处理测试数据 tinyUF.txt 时的完整轨迹。

复制代码
public int find(int p)
{ return id[p]; }
public void union(int p, int q)
{ // 将 p 和 q 归并到相同的分量中
int pID = find(p);
int qID = find(q);
// 如果 p 和 q 已经在相同的分量之中则不需要采取任何行动
if (pID == qID) return;
// 将 p 的分量重命名为 q 的名称
for (int i = 0; i < id.length; i++)
if (id[i] == pID) id[i] = qID;
count--;
}
quick-find

表 1.5.2 quick-find 概览

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

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

图 1.5.3 quick-find 的轨迹

评论

发布