問(wèn)題描述：
動(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ì)都不能說(shuō)明p和q是相連的，那么則將這一對(duì)整數(shù)寫(xiě)入到輸出中案训。
- p和q稱為觸點(diǎn)买置。
- p和q的通道稱為分量粪糙。
quick-union算法比較quick-find算法强霎，提高了union()方法的速度，它算是和quick-find算法師互補(bǔ)的蓉冈。
quick-union源碼：
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class UF {
private int[] id;// 分量id(以觸點(diǎn)作為索引)
private int count;// 分量數(shù)量
public UF(int N) {
count = N;
id = new int[N];
// 初始化分量id
for (int i = 0; i < N; i++) {
id[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 pRoot = find(p);
int qRoot = find(q);
if (pRoot != qRoot) {
return;
}
id[pRoot] = qRoot;
count--;
}
public static void main(String[] args) {
int N = StdIn.readInt();
UF uf = new UF(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");
}
}
程序輸入取自tinyUF.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ù)量
UF uf = new UF(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) {
// 將p和q的根節(jié)點(diǎn)統(tǒng)一
int pRoot = find(p);
int qRoot = find(q);
if (pRoot != qRoot) {
return;
}
id[pRoot] = qRoot;
count--;
}
算法復(fù)雜度分析
- quick-union與quick-find基于同樣的數(shù)據(jù)結(jié)構(gòu)————以觸點(diǎn)作為索引的id[]數(shù)組城舞。
但實(shí)際上他實(shí)現(xiàn)了樹(shù)的數(shù)據(jù)結(jié)構(gòu)。 - 分析quick-union算法的成本比分析quick-find算法的成本更困難寞酿，因?yàn)檫@依賴于輸入的特點(diǎn)家夺。
- 在最好的情況下，find()只需要訪問(wèn)數(shù)組一次就能得到一個(gè)觸點(diǎn)所在分量的標(biāo)識(shí)符伐弹。
- 而在最壞的情況下拉馋，這需要2N-1次數(shù)組訪問(wèn)。
- 由此我們不難構(gòu)造一個(gè)最佳的輸入情況，使得用例的時(shí)間復(fù)雜度為線性級(jí)別煌茴。
- 我們也可以構(gòu)造一個(gè)最壞的輸入随闺，讓用例的運(yùn)行時(shí)間是平方級(jí)別。
