本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
算法(第4版)
知识点
- 数组的访问次数
- quick-union 算法
题目
1.5.2 使用 quick-union 算法（请见 1.5.2.3 节代码框）完成练习 1.5.1。另外，在处理完输入的每对整数之后画出 id[] 数组表示的森林。
1.5.2 Do Exercise 1.5.1, but use quick-union(page224).In addition, draw the forest of trees represented by the id[] array after each input pair is processed.
分析
类比quick-find，我们可以写出quick-union的代码如下：
public class QuickUnion {
private int[] id; // access to component id (site indexed)
private int count; // number of components
public QuickUnion(int N){
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
}
}
private int find(int p)
{
// Find component name.
while (p != id[p]) p = id[p];
return p;
}
public void union(int p, int q)
{ // Give p and q the same root.
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) return;
id[pRoot] = qRoot;
count--;
}
}
测试用例的代码如下：
public static void main(String[] args){
QuickUnion find = new QuickUnion(10);
find.union(9,0);
find.union(3,4);
find.union(5,8);
find.union(7,2);
find.union(2,1);
find.union(5,7);
find.union(0,3);
find.union(4,2);
}
同理，我们可以对QuickUnion稍加改动，计算数组被访问的次数
public class QuickUnionTimes {
private int[] id; // access to component id (site indexed)
private int count; // number of components
//数组访问次数
int eachDoUnionArrayAccessTimes = 0;
public QuickUnionTimes(int N){
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
}
}
private int find(int p)
{
// Find component name.
while (p != id[p]) {
p = id[p];
eachDoUnionArrayAccessTimes += 2;
}
eachDoUnionArrayAccessTimes++;
return p;
}
public void union(int p, int q)
{ // Give p and q the same root.
boolean printDetail = true;
if (printDetail) {
eachDoUnionArrayAccessTimes = 0;
System.out.println("开始联通分量"+p+"和"+q);
}
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot)
return;
id[pRoot] = qRoot;
eachDoUnionArrayAccessTimes++;
count--;
/************************/
if (printDetail) {
/***
* 以下代码输出数组元素
*/
System.out.print("id:{");
for (int i = 0; i < id.length; i++) {
if (i == id.length - 1) {
System.out.print(id[i]);
} else {
System.out.print(id[i] + ",");
}
}
System.out.print("}");
System.out.println("");
}
System.out.println("数组访问的次数:"+eachDoUnionArrayAccessTimes);
}
public static void main(String[] args){
QuickUnion find = new QuickUnion(10);
find.union(9,0);
find.union(3,4);
find.union(5,8);
find.union(7,2);
find.union(2,1);
find.union(5,7);
find.union(0,3);
find.union(4,2);
}
}
以上代码可以在QuickUnionTimes.java找到。
我们可以看到如下输出：
开始联通分量9和0
id:{0,1,2,3,4,5,6,7,8,0}
数组访问的次数:3
开始联通分量3和4
id:{0,1,2,4,4,5,6,7,8,0}
数组访问的次数:3
开始联通分量5和8
id:{0,1,2,4,4,8,6,7,8,0}
数组访问的次数:3
开始联通分量7和2
id:{0,1,2,4,4,8,6,2,8,0}
数组访问的次数:3
开始联通分量2和1
id:{0,1,1,4,4,8,6,2,8,0}
数组访问的次数:3
开始联通分量5和7
id:{0,1,1,4,4,8,6,2,1,0}
数组访问的次数:9
开始联通分量0和3
id:{4,1,1,4,4,8,6,2,1,0}
数组访问的次数:5
开始联通分量4和2
id:{4,1,1,4,1,8,6,2,1,0}
数组访问的次数:5
明显可以看到，比起quick-find，访问数组的次数减少了。
答案
见分析
