【圖解演算法】並查集 —— 聯合查詢演算法

WIKIWIKI 告訴我 —— 何為並查集

在電腦科學中,並查集(Union-Find)是一種樹型的資料結構,用於處理一些不相交集合(Disjoint Sets)的合併及查詢問題。 並查集存在兩個操作(1.union 聯合 2.find 查詢) 和一個需要解答的問題(1.isConnected 或 isSameSet 是否是相互連線,或者說是否在同一個集中)

思考幾個問題

  • wiki 告訴我們並查集這種資料結構可以解決一個問題(可以考察兩個節點是否相通),那麼並查集可以解決那些實際問題呢?
  • 我們實現並查集這種資料結構需要幾個步驟呢(union、find、isConnected…)?

實現

我們這裡直接採用基於 Rank 合併(合併時將元素所在深度小的集合合併到元素所在深度大的集合)方式的實現。

我們還是先看圖

UF

我們在這兒可以回答一下上面提出的第二個問題,實現並查集所需要的幾個步驟:
1. 初始化元素
2. 實現元素與元素間的聯合操作
3. 實現查詢元素所在樹的根節點
4. 解決一個問題,判定兩個元素是否在同一棵樹上(兩個元素是否相互連線)

再來看程式碼

public class UnionFind {
private int[] parent;   // 標註當前元素的父節點的位置
private int[] rank;     // 標註當前元素的層級數
private int size;       // 並查集中的元素個數
public UnionFind (int size){
this.size = size;
parent = new int[size];
rank = new int[size];
init();
}
private void init() {
for (int i = 0; i < size; i  ) {
// 初始化時所有的節點的父節點指向本身,所有的元素層級均為 1
parent[i] = i;
rank[i] = 1;
}
}
/**
* 尋找當前節點的根節點元素
* @param target
* @return
*/
public int find(int target) {
if(target >= size)
throw new ArrayIndexOutOfBoundsException();
if(target == parent[target])
return target;
return find(parent[target]);
}
/**
* 連線兩個元素
* @param p
* @param q
*/
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot)
return;
if(rank[pRoot] > rank[qRoot]) { // p 所在的樹的高度比 q 所在輸的高度高,這時應該讓 q 的根節點元素連線到 p 的根節點元素
parent[qRoot] = pRoot; // 此時樹的高度不變
} else if(rank[pRoot] < rank[qRoot]) {
parent[pRoot] = qRoot; // 此時樹的高度不變
} else {
parent[pRoot] = qRoot; // 此時樹的高度  1
rank[qRoot]  = 1;
}
}
/**
* 判斷兩個節點是否連線
* @param p
* @param q
* @return
*/
public boolean isConnected(int p, int q) {
// 如果兩個節點的根節點一致則表示這兩個節點是相連線的
return find(p) == find(q);
}
}

測試類:

public static void main(String[] args) {
int size = 10;
// Step 1: init()
UnionFind uf = new UnionFind(size);
// Step 2: union()
uf.union(1,2);
uf.union(3,4);
uf.union(0,9);
uf.union(4,7);
uf.union(6,5);
uf.union(5,8);
uf.union(3,9);
uf.union(1,8);
// Step 3: find()
System.out.println(uf.find(0));     // 9
System.out.println(uf.find(1));     // 5
System.out.println(uf.find(2));     // 5
System.out.println(uf.find(3));     // 9
System.out.println(uf.find(4));     // 9
System.out.println(uf.find(5));     // 5
System.out.println(uf.find(6));     // 5
System.out.println(uf.find(7));     // 9
System.out.println(uf.find(8));     // 5
System.out.println(uf.find(9));     // 9
// Step 4: isConnected
System.out.println(uf.isConnected(0,1));    // false
System.out.println(uf.isConnected(1,2));    // true
System.out.println(uf.isConnected(3,4));    // true
System.out.println(uf.isConnected(5,6));    // true
System.out.println(uf.isConnected(7,8));    // false
System.out.println(uf.isConnected(8,9));    // false
System.out.println(uf.isConnected(2,4));    // false
System.out.println(uf.isConnected(3,5));    // false
System.out.println(uf.isConnected(5,6));    // true
System.out.println(uf.isConnected(7,9));    // true
}

我們可以分解這幾歩操作

Step 1: init()

init

Step 2: union()

union

Step 3: find()

if(target == parent[target]) 
return target;
return find(parent[target]);

遞迴去尋找目標的父親節點,直到尋找到根節點為止

Step 4: isConnected()

return find(p) == find(q);

考察兩個節點的根節點是否是同一個,即考察兩個節點是否在同一棵樹上。

更多關於並查集

https://blog.csdn.net/dm_vincent/article/details/7655764

圖解演算法目錄

【圖解演算法】排序演算法——氣泡排序、選擇排序

【圖解演算法】排序演算法——插入排序

【圖解演算法】排序演算法——歸併排序

【圖解演算法】排序演算法——快速排序

【圖解演算法】Java GC演算法

【圖解演算法】排序演算法——堆排序

【圖解演算法】並查集 —— 聯合查詢演算法

Gif Power By https://visualgo.net