問題提出
一個(gè)集合中有N個(gè)點(diǎn)，N個(gè)點(diǎn)中有許多的相連的，任意給出兩個(gè)點(diǎn)，如何才能快速地知道這兩個(gè)點(diǎn)是否是相連(間接相連也算)的 ? 如果不相連，如何才能快速高效地實(shí)現(xiàn)連接？這樣的問題在計(jì)算機(jī)網(wǎng)絡(luò)的連接和電子電路中都有出現(xiàn)。
設(shè)計(jì)API
為了說明問題，我們?cè)O(shè)計(jì)了一份API來封裝所需要的基本操作：初始化整個(gè)集合，連接兩個(gè)點(diǎn)，判斷包含兩個(gè)點(diǎn)的一條連接鏈，判斷兩個(gè)點(diǎn)是否相連，返回鏈的數(shù)量。
//public class UF
// UF(int N) 初始化整個(gè)集合
// void union(int p, int q) 在p,q之間添加一條連接
// int find(int p) p所在的鏈的標(biāo)識(shí)符
// boolean connected(int p, int q) 如果p和q存在于同一條鏈之中則返回true
// int count() 統(tǒng)計(jì)集合中鏈的數(shù)量
//
當(dāng)初始化所有的點(diǎn)組成的集合的時(shí)候，用1～N－1來表示所有的點(diǎn)。如果兩個(gè)點(diǎn)在不同的鏈當(dāng)中，可以用union來將兩條鏈連接，find方法用來返回某個(gè)點(diǎn)所在的連通鏈的標(biāo)識(shí)符，connected用來判斷兩個(gè)點(diǎn)是否相連（即是否在一條鏈上），count方法用來返回整個(gè)集合當(dāng)中鏈的條數(shù)。
在我們的實(shí)現(xiàn)當(dāng)中，我們將使用一個(gè)大小為N的數(shù)組來表示N個(gè)點(diǎn)，數(shù)組的index即是每一個(gè)點(diǎn)的名稱，每個(gè)index下存儲(chǔ)的東西就是該點(diǎn)所屬鏈的標(biāo)識(shí)符。
最初版本的實(shí)現(xiàn)－quick find
import java.util.Scanner;
public class UF {
private int[] id; //分量id,以觸點(diǎn)作為索引
private int count; //分量數(shù)量
public UF(int N){
count = N;
id = new int[N];
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){
return id[p];
}
public void union(int p , int q){
//將p和q所屬的分量歸并(連接兩條鏈)
int pID = find(p);
int qID = find(q);
//如果p和q已經(jīng)在相同的分量當(dāng)中則不需要采取任何行動(dòng)
if (pID==qID) return;
for (int i = 0; i < id.length; i++){
if (id[i] == pID) id[i] = qID;
}
count--;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
System.out.println("Input the length of array!");
int N = sc.nextInt();
UF uf = new UF(N);
while (sc.hasNext()){
int p = sc.nextInt();
int q = sc.nextInt();
if (uf.connected(p,q)) continue;
uf.union(p,q);
System.out.println(p+""+q);
}
System.out.println(uf.count + "components");
}
}
這一實(shí)現(xiàn)方案在檢查兩個(gè)點(diǎn)是否連接是效率非常的高，然而在連接兩條鏈?zhǔn)切蕝s十分低下。例如p所在的分量的標(biāo)識(shí)符為1，q所在的分量的標(biāo)識(shí)符為2，當(dāng)想把p和q所在的分量歸并的時(shí)候，就需要遍歷整個(gè)數(shù)組，將所有標(biāo)識(shí)符為1的索引里的標(biāo)識(shí)符改為2。這樣就導(dǎo)致當(dāng)我們將N個(gè)點(diǎn)全部連通的時(shí)候，調(diào)用了union方法N-1次，union方法里面又一個(gè)循環(huán)，這就相當(dāng)于是兩個(gè)循環(huán)，所以這個(gè)算法的運(yùn)行時(shí)間對(duì)于得到少量連通分量的應(yīng)用來說是平方級(jí)別的。當(dāng)使用100萬個(gè)點(diǎn)和200萬條連接的時(shí)候，這個(gè)算法運(yùn)行了幾十分鐘。
第一次改進(jìn)后的實(shí)現(xiàn)－quick union
import java.util.Scanner;
public class UF {
private int[] id; //分量id,以觸電作為索引
private int count; //分量數(shù)量
public UF(int N){
count = N;
id = new int[N];
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){
Scanner sc = new Scanner(System.in);
System.out.println("Input the length of array!");
int N = sc.nextInt();
UF uf = new UF(N);
while (sc.hasNext()){
int p = sc.nextInt();
int q = sc.nextInt();
if (uf.connected(p,q)) continue;
uf.union(p,q);
System.out.println(p+""+q);
}
System.out.println(uf.count + "components");
}
}
這一次的改進(jìn)主要是為了加快union算法的速度。這一次我們不是使用一條鏈上的點(diǎn)用同一個(gè)標(biāo)識(shí)符的方式，而是使用類似于鏈表的方式，比如點(diǎn)1和點(diǎn)2相連，就在索引2里面放置值1，而獨(dú)立的一個(gè)點(diǎn)則索引和里面放置的值都是索引值。在這個(gè)算法里面，find方法顯然比上面要慢一些，確定任意兩個(gè)點(diǎn)是否連通的方式是分別由兩個(gè)點(diǎn)的索引里面所存的下一個(gè)節(jié)點(diǎn)的索引一路上溯到它們所在的鏈的根節(jié)點(diǎn)，如果是同一個(gè)根節(jié)點(diǎn)，那么就是連通的，否則就不連通，如果想要他們連通，就使用改良后的union方法將兩個(gè)根節(jié)點(diǎn)連接起來－－由其中一個(gè)根節(jié)點(diǎn)的索引中存儲(chǔ)另一個(gè)根節(jié)點(diǎn)的索引值。然而這種改良在很多情況下并沒有比未改良的方法快（簡(jiǎn)單分析和實(shí)踐都已經(jīng)證明），而且在一種特殊的輸入下：01，12，23，34，45，……這個(gè)鏈會(huì)變成一條超長(zhǎng)的鏈表，而不是樹的形狀，這樣就和未改進(jìn)沒有區(qū)別，依然類似于遍歷數(shù)組。
第二次改進(jìn)后的實(shí)現(xiàn)－加權(quán)quick-union算法
幸運(yùn)的是，我們只需要稍微改變一下上面的算法，就能保證上面的問題不再出現(xiàn)。
與其胡亂的將一棵樹連接到另一棵樹，我們更應(yīng)該總是將一棵較小的樹添加到一棵較大的樹上,這樣我們就能夠限制樹的高度，從而保證查找的時(shí)間復(fù)雜度為lgN。
import java.util.Scanner;
public class UF {
private int[] id; //分量id,以觸點(diǎn)作為索引
private int[] size; //由觸電索引的各個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的分量的大小
private int count; //分量數(shù)量
public UF(int N){
count = N;
id = new int[N];
for (int i = 0;i < N;i++){
id[i] = i;
}
size = new int[N];
for (int i = 0;i < N;i++){
size[i] = 1;
}
}
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;
if (size[pRoot] < size[qRoot]){
id[pRoot] = id[qRoot];
size[qRoot] += size[pRoot];
}else {
id[qRoot] = id[pRoot];
size[pRoot] += size[qRoot];
}
count--;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
System.out.println("Input the length of array!");
int N = sc.nextInt();
UF uf = new UF(N);
while (sc.hasNext()){
int p = sc.nextInt();
int q = sc.nextInt();
if (uf.connected(p,q)) continue;
uf.union(p,q);
System.out.println(p+""+q);
}
System.out.println(uf.count + "components");
}
}
這樣就能保證在將N個(gè)節(jié)點(diǎn)完全連接起來的時(shí)候的時(shí)間復(fù)雜度為NlgN，這樣的時(shí)間復(fù)雜度已經(jīng)復(fù)合解決很多大型問題的要求。
最優(yōu)算法－路徑壓縮的加權(quán)quick-union算法
在理想情況下，我們都希望所有的節(jié)點(diǎn)都直接連接在它的根節(jié)點(diǎn)上，這樣就只需一次操作就能找到其根節(jié)點(diǎn)，能表現(xiàn)出常數(shù)時(shí)間，這種方法被稱為路徑壓縮方法。
public int find(int p){
int temp = p;
while (p != id[p]) p = id[p];
id[temp] = id[p];
return p;
}
將find方法如此修改就可以實(shí)現(xiàn)路徑壓縮。
此時(shí)quick-union算法的速度已經(jīng)比一開始的時(shí)候快了很多很多。
資源以及參考
本筆記是學(xué)習(xí)普林斯頓大學(xué)算法課程以及閱讀其教材《算法》第四版所作
用于跑著玩的擁有100萬個(gè)點(diǎn)和200萬條鏈接的文件(直接下載鏈接文件即可)
http://algs4.cs.princeton.edu/15uf/largeUF.txt
命令行運(yùn)行：
cd到.java文件所在文件夾，執(zhí)行一下命令，如果.java文件中含有包名，注意將其刪除
% javac UF.java
% java UF < largeUF.txt
