算法练习(91):quick-union(1.5.2)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：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，访问数组的次数减少了。

答案

见分析

代码索引

QuickUnion.java