問題描述：
動(dòng)態(tài)連通性：輸入為一列整數(shù)對(duì)契沫，其中每個(gè)整數(shù)對(duì)都表示一個(gè)某種弄類型的對(duì)象，一堆整數(shù)p q可以被理解為“p和q是相連的”。當(dāng)程序從輸入中讀取了整數(shù)對(duì)p q時(shí)，如果一直的所有整數(shù)對(duì)都不能說明p和q是相連的瓶摆，那么則將這一對(duì)整數(shù)寫入到輸出中凉逛。
- p和q稱為觸點(diǎn)性宏。
- p和q的通道稱為分量。
加權(quán)的quick-union算法比較quick-union算法状飞，在union()隨意連接樹的時(shí)候毫胜，添加了一個(gè)數(shù)組和一些代碼來記錄樹中的節(jié)點(diǎn)數(shù)书斜，從而總是將較小的數(shù)連接到較大的數(shù)上。
加權(quán)的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個(gè)數(shù),每個(gè)數(shù)的ID都指向自己
while(!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
// 讀取一個(gè)整數(shù)對(duì)
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();// 讀取觸點(diǎn)數(shù)量
WeightedQuickUnionUF uf = new WeightedQuickUnionUF(N);// 初始化N個(gè)分量
while(!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();// 讀取整數(shù)對(duì)
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--;
}
算法復(fù)雜度分析
- 對(duì)于N個(gè)觸點(diǎn)酵使，加權(quán)quick-union算法構(gòu)造的森林中的任意節(jié)點(diǎn)的深度最多為lgN荐吉。
- 對(duì)于加權(quán)quick-union算法和N個(gè)觸點(diǎn)，在最壞情況下find()口渔、connected()和union()的成本的增長(zhǎng)數(shù)量級(jí)為㏒N样屠。
