定義
就是有“合并集合”和“查找集合中的元素”兩種操作的關于資料結構的一種算法。
- 連接配接兩個對象
- 判斷是否這兩個對象是連接配接的
上例中，0,7是沒有路徑的；8,9之間有一條可達路徑，是以是連接配接的。
模組化
關于連接配接
- 等價性： p連接配接到p,每個對象都能連接配接到自己
- 對稱性： p連接配接到q;等價于q連接配接到p
- 傳遞性： 如果p連接配接到q,q連接配接到r,那麼,p連接配接到r。
快速查找
資料結構
這裡用到的資料結構是數組。
- 對象索引整數數組，用索引來表示N個對象，0表示第一個對象，以此類推。
- 如果p和q是連接配接的，那麼它們數組的值相同。
查找
隻需要檢查p和q是否有相同的值。
合并
将它們的值設為相同的。假如需要合并兩個分别包含p和q的子集，将所有值等于idp的對象的值改為id[q]，即改為q的值。
實作
初始化、判斷連接配接以及合并
public class QuickFindUF
private int [] id;
public QuickFindUF(int N){
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i; //初始化
}
}
/**
* 判斷p和q是否是連接配接的
* @param p
* @param q
* @return
public boolean connected(int p,int q){
return id[p] == id[q];
}
/**
* 合并p的子集和q的子集
* 将所有值等于id[p]的對象的值改為id[q]
* @param p
* @param
public void union(int p,int q){
int pid = id[p];
int qid = id[q];
for (int i = 0; i < id.length; i++) {
if(id[i] == pid){
id[i] = qid;
}
}
}
} 時間複雜度分析
| 算法 | 初始化 | 合并 | 查詢 |
| quick-find | N | N | 1 |
在這個實作中，合并操作的代價太高了。如果需要在N個對象上進行N次合并，那就是O(n^2)。效率不高。
快速合并
資料結構
也是數組。
- 對象索引整數數組，用索引來表示N個對象，0表示第一個對象，以此類推。
- id[i]存放的值代表i的父節點索引
- 若id[i]==i，則說明i是根節點
上面3的父節點是4,4的父節點是9,9的父節點也是9,9為根節點。
查找
檢查p和q根節點是否相同。
合并
合并操作就非常簡單了。
要合并p,q兩個對象的分量(合并樹)，将p的根節點設為q的根節點(p=>q p的根節點指向q)。
上面隻需要将9的值改為6即可。
實作
public class QuickUnionUF
private int [] id;
public QuickUnionUF(int N){
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
}
}
/**
* 找到i的根節點
* @param i
* @return
private int root(int i){
while(i != id[i]){
i = id[i];//i和id[i] 一起更新
}
return i;
}
/**
* 判斷p和q是否是連接配接的
* @param p
* @param q
* @return
public boolean connected(int p,int q){
return root(p) == root(q);
}
/**
* 合并p和q
* 将p的根節點設為q的根節點(p=>q p的根節點指向q)。
* @param p
* @param
public void union(int p,int q){
int qroot = root(q);//找到q的根節點
int 時間複雜度分析
| 算法 | 初始化 | 合并 | 查詢 |
| quick-find | N | N | 1 |
| quick-union | N | N | N |
最壞的情況下，會生成一顆瘦長樹。
權重快速合并(Weighted quick-union)
資料結構
與快速合并類似，但是維護了一個額外的數組sz[i],它包含了以i為根節點的樹的節點數量。
查找
與快速合并完全相同
合并
- 将小樹指向大樹的根節點
- 更新sz[]數組
實作
package com.algorithms.UnionFind;
public class WeightedQuickUnionUF
private int [] id;
private int [] sz;//size of component for roots
private int count;//number of components
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] = 1;
}
public int count(){
return count;
}
/**
* 找到i的根節點
* @param i
* @return
private int root(int i){
while(i != id[i]){
i = id[i];//i和id[i] 一起更新
}
return i;
}
/**
* 判斷p和q是否是連接配接的
* @param p
* @param q
* @return
public boolean connected(int p,int q){
return root(p) == root(q);
}
/**
* 合并p和q
* 将p的根節點設為q的根節點(p=>q p的根節點指向q)。
* @param p
* @param
public void union(int p,int q){
int i = root(q);
int j = root(p);
if( i == j) return;
//Make smaller root point to larger one.
if(sz[i] <sz[j]){
id[i] = j;
sz[j] += sz[i];
}else{
id[j] = i;
sz[i] += sz[j];
}
count --;
}
} | 算法 | 初始化 | 合并 | 查詢 |
| quick-find | N | N | 1 |
| quick-union | N | N+ | N |
| Weighted quick-union | N | lgN+ | lgN |
+
加上查找根節點的消耗
*
樹中任意節點的深度，最大是lgN (以2為底)
但是，還能再改進！
路徑壓縮
在計算p節點的根後，将每個經過的節點都指向根。
上圖中，從p找到根0，需要經過9(當然要包括自己),6,3,1(已經指向根節點了)這些節點。讓它們都指向根：
如果要實作完全展平，會很複雜。我們可以選擇一種折中的方案，将節點p指向節點p的祖父(父節點的父節點)節點。
神奇的是，代碼隻需要在權重快速合并的基礎上，進行一些小的改動:
将路徑上的每個節點指向它的祖父節點：
private int root(int i){
while(i != id[i]){
id[i] = id[id[i]];//(父節點的父節點)
i = id[i];//i和id[i] 一起更新
}
return