问题描述：
动态连通性：输入为一列整数对，其中每个整数对都表示一个某种弄类型的对象，一堆整数p q可以被理解为“p和q是相连的”。当程序从输入中读取了整数对p q时，如果一直的所有整数对都不能说明p和q是相连的，那么则将这一对整数写入到输出中。
- p和q称为触点。
- p和q的通道称为分量。
加权的quick-union算法比较quick-union算法，在union()随意连接树的时候，添加了一个数组和一些代码来记录树中的节点数，从而总是将较小的数连接到较大的数上。
加权的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个数,每个数的ID都指向自己
while(!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
// 读取一个整数对
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();// 读取触点数量
WeightedQuickUnionUF uf = new WeightedQuickUnionUF(N);// 初始化N个分量
while(!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();// 读取整数对
if (uf.connected(p, q)) continue;// 如果已经连通则忽略
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算法构造的森林中的任意节点的深度最多为lgN。
- 对于加权quick-union算法和N个触点，在最坏情况下find()、connected()和union()的成本的增长数量级为㏒N。
