并查集裡的 find 函數裡可以進行路徑壓縮，是為了更快速的查找一個點的根節點。對于一個集合樹來說，它的根節點下面可以依附着許多的節點，是以，我們可以嘗試在 find 的過程中，從底向上，如果此時通路的節點不是根節點的話，那麼我們可以把這個節點盡量的往上挪一挪，減少數的層數，這個過程就叫做路徑壓縮。
如下圖中，find(4) 的過程就可以路徑壓縮，讓樹的層數更少。
節點 4 往上尋找根節點時，壓縮第一步，樹的層數就減少了一層：
節點 2 向上尋找，也不是根節點，那麼把元素 2 指向原來父節點的父節點，操後後樹的層數相應減少了一層，同時傳回根節點 0。
find 過程代碼修改為 ：
// 查找過程, 查找元素p所對應的集合編号
// O(h)複雜度, h為樹的高度
private int find(int p){
assert( p >= 0 && p < count );
// path compression 1
while( p != parent[p] ){
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
上述路徑壓縮并不是最優的方式，我們可以把最初的樹壓縮成下圖所示，層數是最少的。
這個 find 過程代表表示為:
...
private int find(int p) {
assert (p >= 0 && p < count);
//第二種路徑壓縮算法
if (p != parent[p])
parent[p] = find(parent[p]);
return parent[p];
源碼包下載下傳：Download
package runoob.union;
/**
* 基于rank的優化
*/
public class UnionFind4 {
private int[] rank; // rank[i]表示以i為根的集合所表示的樹的層數
private int[] parent; // parent[i]表示第i個元素所指向的父節點
private int count; // 資料個數
// 構造函數
public UnionFind4(int count){
rank = new int[count];
parent = new int[count];
this.count = count;
// 初始化, 每一個parent[i]指向自己, 表示每一個元素自己自成一個集合
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
// 查找過程, 查找元素p所對應的集合編号
// O(h)複雜度, h為樹的高度
private int find(int p){
assert( p >= 0 && p < count );
// 不斷去查詢自己的父親節點, 直到到達根節點
// 根節點的特點: parent[p] == p
while( p != parent[p] )
p = parent[p];
return p;
//第二種路徑壓縮算法
//if( p != parent[p] )
//parent[p] = find( parent[p] );
//return parent[p];
// 檢視元素p和元素q是否所屬一個集合
public boolean isConnected( int p , int q ){
return find(p) == find(q);
// 合并元素p和元素q所屬的集合
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
if( rank[pRoot] < rank[qRoot] ){
parent[pRoot] = qRoot;
else if( rank[qRoot] < rank[pRoot]){
parent[qRoot] = pRoot;
else{ // rank[pRoot] == rank[qRoot]
rank[qRoot] += 1; // 維護rank的值