問題描述：

動態(tài)連通性：輸入為一列整數(shù)對，其中每個整數(shù)對都表示一個某種弄類型的對象，一堆整數(shù)p q可以被理解為“p和q是相連的”。當程序從輸入中讀取了整數(shù)對p q時，如果一直的所有整數(shù)對都不能說明p和q是相連的，那么則將這一對整數(shù)寫入到輸出中。

• p和q稱為觸點。
• p和q的通道稱為分量。

加權的quick-union算法比較quick-union算法，在union()隨意連接樹的時候，添加了一個數(shù)組和一些代碼來記錄樹中的節(jié)點數(shù)，從而總是將較小的數(shù)連接到較大的數(shù)上。

加權的quick-union源碼：

package cn.lemon.together;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class WeightedQuickUnionUF {
    private int[] id;
    private int[] sz;
    private int count;

    public WeightedQuickUnionUF(int N) {
        count = N;
        id = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
        }
        sz = new int[N];
        for (int i = 0; i < N; i++) {
            sz[i] = i;
        }
    }
    public int count() {
        return count;
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public int find(int p) {
        while(p != id[p]) {
            p = id[p];
        }
        return p;
    }

    public void union(int p, int q) {
        int i = find(p);
        int j = find(q);
        if (i == j) return;
        if (sz[i] < sz[j]) {id[i] = j; sz[j] += sz[i];}
        else               {id[j] = i; sz[i] += sz[j];}
        count--;
    }

    public static void main(String[] args) {
        int N = StdIn.readInt();
        WeightedQuickUnionUF uf = new WeightedQuickUnionUF(N);// 初始化N個數(shù),每個數(shù)的ID都指向自己
        while(!StdIn.isEmpty()) {
            int p = StdIn.readInt();
            int q = StdIn.readInt();
            // 讀取一個整數(shù)對
            if (!uf.connected(p, q)) {
                uf.union(p, q);
                StdOut.println(p + " " + q);
            }

        }
        StdOut.println(uf.count + " components");
    }
}

程序輸入取自largeUF.text文件:

10
4 3
3 8
6 5
9 4
2 1
8 9
5 0
7 2
6 1
1 0
6 7

程序入口

public static void main(String[] args) {
    int N = StdIn.readInt();// 讀取觸點數(shù)量
    WeightedQuickUnionUF uf = new WeightedQuickUnionUF(N);// 初始化N個分量
    while(!StdIn.isEmpty()) {
        int p = StdIn.readInt();
        int q = StdIn.readInt();// 讀取整數(shù)對
        if (uf.connected(p, q)) continue;// 如果已經(jīng)連通則忽略
        uf.union(p, q);// 歸并分量
        StdOut.println(p + " " + q);// 打印鏈接
    }
    StdOut.println(uf.count + " components");
}

算法邏輯分析

public int find(int p) {
    while(p != id[p]) {
        p = id[p];
    }
    return p;
}

public void union(int p, int q) {
    int i = find(p);
    int j = find(q);
    if (i == j) return;
    if (sz[i] < sz[j]) {id[i] = j; sz[j] += sz[i];}
    else               {id[j] = i; sz[i] += sz[j];}
    count--;
}

算法復雜度分析

• 對于N個觸點，加權quick-union算法構造的森林中的任意節(jié)點的深度最多為lgN。
• 對于加權quick-union算法和N個觸點，在最壞情況下find()、connected()和union()的成本的增長數(shù)量級為㏒N。