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

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

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

(提高题)

1.5.12 使用路径压缩的 quick-union 算法。根据路径压缩修改 quick-union 算法(请见 1.5.2.3 节),在 find() 方法中添加一个循环来将从 p 到根节点的路径上的每个触点都连接到根节点。给出一列输入,使该方法能够产生一条长度为 4 的路径。注意:该算法的所有操作的均摊成本已知为对数级别。

1.5.13 使用路径压缩的加权 quick-union 算法。修改加权 quick-union 算法(算法 1.5),实现如练习 1.5.12 所述的路径压缩。给出一列输入,使该方法能够产生一棵高度为 4 的树。注意:该算法的所有操作的均摊成本已知被限制在反 Ackermann 函数的范围之内,且对于实际应用中可能出现的所有 N 值均小于 5。

1.5.14 根据高度加权的 quick-union 算法。给出 UF 的一个实现,使用和加权 quick-union 算法相同的策略,但记录的是树的高度并总是将较矮的树连接到较高的树上。用算法证明 N 个触点的树的高度不会超过其大小的对数级别。

1.5.15 二项树。请证明,对于加权 quick-union 算法,在最坏情况下树中每一层的节点数均为二项式系数。在这种情况下,计算含有 N=2n 个节点的树中节点的平均深度。

1.5.16 均摊成本的图像。修改你为练习 1.5.7 给出的实现,绘出如正文所示的均摊成本的图像。

1.5.17 随机连接。设计 UF 的一个用例 ErdosRenyi,从命令行接受一个整数 N,在 0 到 N-1 之间产生随机整数对,调用 connected() 判断它们是否相连,如果不是则调用union() 方法(和我们的开发用例一样)。不断循环直到所有触点均相互连通并打印出生成的连接总数。将你的程序打包成一个接受参数N 并返回连接总数的静态方法count(),添加一个main() 方法从命令行接受N,调用 count() 并打印它的返回值。

1.5.18 随机网格生成器。编写一个程序 RandomGrid,从命令行接受一个 intN,生成一个 N×N 的网格中的所有连接。它们的排列随机且方向随机(即 (p q) 和 (q p) 出现的可能性是相等的),将这个结果打印到标准输出中。可以使用 RandomBag 将所有连接随机排列(请见练习 1.3.34),并使用如右下所示的 Connection 嵌套类来将 p 和 q 封装到一个对象中。将程序打包成两个静态方法:generate(),接受参数 N 并返回一个连接的数组;main(),从命令行接受参数 N,调用 generate(),遍历返回的数组并打印出所有连接。

复制代码
private class Connection
{
int p;
int q;
public Connection(int p, int q)
{ this.p = p; this.q = q; }
}
封装连接的嵌套类

1.5.19 动画。编写一个 RandomGrid(请见练习 1.5.18)的用例,和我们的开发用例一样使用UnionFind 来检查触点的连通性并在处理的同时用StdDraw 将它们绘出。

1.5.20 动态生长。使用链表或大小可变的数组实现加权 quick-union 算法,去掉需要预先知道对象数量的限制。为 API 添加一个新方法 newSite(),它应该返回一个类型为 int 的标识符。

评论

发布