本系列博客習(xí)題來自《算法(第四版)》，算是本人的讀書筆記，如果有人在讀這本書的，歡迎大家多多交流。為了方便討論，本人新建了一個(gè)微信群(算法交流)，想要加入的，請(qǐng)?zhí)砑游业奈⑿盘?hào)：zhujinhui207407 謝謝。另外，本人的個(gè)人博客 http://www.kyson.cn 也在不停的更新中，歡迎一起討論

算法(第4版)

知識(shí)點(diǎn)

• 數(shù)組的訪問次數(shù)
• quick-union 算法

題目

1.5.2 使用 quick-union 算法（請(qǐng)見 1.5.2.3 節(jié)代碼框）完成練習(xí) 1.5.1。另外，在處理完輸入的每對(duì)整數(shù)之后畫出 id[] 數(shù)組表示的森林。

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--;
    }
}

測(cè)試用例的代碼如下：

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);
}

同理，我們可以對(duì)QuickUnion稍加改動(dòng)，計(jì)算數(shù)組被訪問的次數(shù)

public class QuickUnionTimes {
    private int[] id;     // access to component id (site indexed)
    private int count;    // number of components
    //數(shù)組訪問次數(shù)
    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("開始聯(lián)通分量"+p+"和"+q);
        }
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot)
            return;
        id[pRoot] = qRoot;
        eachDoUnionArrayAccessTimes++;
        count--;

        /************************/
        if (printDetail) {
            /***
             * 以下代碼輸出數(shù)組元素
             */
            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("數(shù)組訪問的次數(shù):"+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找到。

我們可以看到如下輸出：

開始聯(lián)通分量9和0
id:{0,1,2,3,4,5,6,7,8,0}
數(shù)組訪問的次數(shù):3
開始聯(lián)通分量3和4
id:{0,1,2,4,4,5,6,7,8,0}
數(shù)組訪問的次數(shù):3
開始聯(lián)通分量5和8
id:{0,1,2,4,4,8,6,7,8,0}
數(shù)組訪問的次數(shù):3
開始聯(lián)通分量7和2
id:{0,1,2,4,4,8,6,2,8,0}
數(shù)組訪問的次數(shù):3
開始聯(lián)通分量2和1
id:{0,1,1,4,4,8,6,2,8,0}
數(shù)組訪問的次數(shù):3
開始聯(lián)通分量5和7
id:{0,1,1,4,4,8,6,2,1,0}
數(shù)組訪問的次數(shù):9
開始聯(lián)通分量0和3
id:{4,1,1,4,4,8,6,2,1,0}
數(shù)組訪問的次數(shù):5
開始聯(lián)通分量4和2
id:{4,1,1,4,1,8,6,2,1,0}
數(shù)組訪問的次數(shù):5

明顯可以看到，比起quick-find，訪問數(shù)組的次數(shù)減少了。

答案

見分析

代碼索引

QuickUnion.java