並查集演算法Union-Find的思想、實現以及應用
並查集演算法，也叫Union-Find演算法，主要用於解決圖論中的動態連通性問題。
Union-Find演算法類
這裡直接給出並查集演算法類UnionFind.class，如下：
/**
* Union-Find 並查集演算法
* @author Chiaki
*/
public class UnionFind {
// 連通分量個數
private int count;
// 存儲若干棵樹
private int[] parent;
// 記錄樹的"重量"
private int[] size;
// 構造函數
public UnionFind(int count) {
this.count = count;
parent = new int[count];
size = new int[count];
for (int i = 0; i < count; i++) {
parent[i] = i;
size[i] = 1;
}
}
// 連通函數
public void union(int p, int q) {
// 如果節點p和q已經連接，直接返回
if (connected(p,q)) return;
// 找到節點p和節點q的根節點
int rootP = find(p);
int rootQ = find(q);
if (size[rootP] > size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
} else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
count--;
}
// 判斷是否連通
public boolean connected(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
return rootP == rootQ;
}
// 尋找根節點
public int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
// 返回連通分量個數
public int count() {
return count;
}
}
下面逐步解釋Union-Find演算法類中的變數定義以及相關函數。
成員變數
可以看到該類中定義了三個成員變數，分別是int count、int[] parent以及int[] size。
int count：可以理解為連通分量的個數。
如上左圖所示，共有10個節點（分量），此時連通分量的個數為10。如上右圖所示，在進行連通操作（union）後，分量之間存在了連接關係（connected），因此此時的連通分量個數為6。
int[] parent：定義父節點數組。說到父節點數組，這裡使用多棵樹來表示連通性。規定樹中的每個節點都有一個指針指向其父節點。一開始沒有連通，此時每個節點指向父節點的指針都是指向自己，也就是根節點；當兩個節點被連通，就讓其中的任意一個節點的根節點接到另一個節點的根節點上，如下圖所示。
此時，可以得到：若節點p和節點q連通，那麼它們一定有相同的根節點。
int[] size：記錄每一棵樹中節點的數量，稱之為樹的重量，以此方便對樹的平衡性進行優化。如上張圖所示，如果要把節點3和節點7連接（union），此時樹的情況如下圖所示：
此時，可以看出，樹的平衡性出現了問題，因此我們需要藉助樹的重量，即int[] size數組對節點的連接操作（union）進行平衡性優化。
構造函數
UnionFind類構造函數的參數為int n，即初始的節點數目，亦即初始連通分量的個數。在進行初始化操作時，主要是初始化父節點數組int[] parent以及每棵樹中節點的數目數組int[] size。在初始情況下，每個節點的父節點都是自身，而每棵樹中節點的個數都是1，因此構造函數如下：
public UnionFind(int count) {
this.count = count;
parent = new int[count];
size = new int[count];
for (int i = 0; i < count; i++) {
parent[i] = i;
size[i] = 1;
}
}
其他函數
在上面的介紹中，我們知道，在UnionFind類中最重要的操作就是連接（union）操作。然而，在將節點p和節點q連接時，需要把一個節點（假定為節點p）的指針指向另一個節點（假定為節點q）的父節點，因此，我們需要先實現一個int find(int x)函數來找到一個節點的父節點，如下所示：
public int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
另外，實現boolean connected(int p, int q)函數判斷節點p和節點q是否處於連接狀態，如下：
public boolean connected(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
return rootP == rootQ;
}
在實現int find(int x)函數和boolean connected(int p, int q)函數後，接下來要實現最關鍵的連接操作，即void union(int p, int q)函數，如下所示：
public void union(int p, int q) {
// 如果節點p和q已經連接，直接返回
if (connected(p,q)) return;
// 找到節點p和節點q的根節點
int rootP = find(p);
int rootQ = find(q);
// 根據size數組進行平衡化操作：小樹接到大樹下
if (size[rootP] > size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
} else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
// 連接完成後，連通分量減一
count--;
}
最後，完成連通分量計數函數int count()，如下：
public int count() {
return count;
}
Union-Find演算法應用
在介紹完並查集演算法類UnionFind.class後，下面來看看該演算法的應用。
朋友圈/好友關係問題
這個問題是並查集的一個典型應用，印象中猿輔導的演算法手撕中這個題出現的頻率比較高。問題描述如下：
班上有 N 名學生。其中有些人是朋友，有些則不是。他們的友誼具有是傳遞性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那麼我們可以認為 A 也是 C 的朋友。所謂的朋友圈，是指所有朋友的集合。
給定一個
N * N的矩陣 M，表示班級中學生之間的朋友關係。如果M[i][j]= 1，表示已知第 i 個和 j 個學生互為朋友關係，否則為不知道。你必須輸出所有學生中的已知的朋友圈總數。輸入輸出示例如下：輸入：
[[1,1,0],
[1,1,0],
[0,0,1]]輸出：2
利用並查集來解決該問題（假設UnionFind.class已定義，下同），如下：
class Solution {
public int findCircleNum(int[][] M) {
int n = M.length;
UnionFind uf = new UnionFind(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (M[i][j] == 1) uf.union(i, j);
}
}
return uf.count();
}
}
島嶼數量
島嶼數量問題其實也是互聯網大廠常問的題目之一，除了採用DFS來實現，並查集也可以用於解決這類問題。問題描述如下：
給你一個由 ‘1’（陸地）和 ‘0’（水）組成的的二維網格，請你計算網格中島嶼的數量。島嶼總是被水包圍，並且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。此外，你可以假設該網格的四條邊均被水包圍。輸入輸出示例如下：
輸入：grid = [
[“1″,”1″,”1″,”1″,”0”],
[“1″,”1″,”0″,”1″,”0”],
[“1″,”1″,”0″,”0″,”0”],
[“0″,”0″,”0″,”0″,”0”]
]輸出：1
採用並查集方法解決：
class Solution {
public int numIslands(char[][] grid) {
int r = grid.length;
if (r == 0) return 0;
int c = grid[0].length;
int size = r * c;
// 方向數組（向下和向右的坐標偏移）
int[][] directions = {{1, 0}, {0, 1}};
// +1表示虛擬水域，認為網格四條邊被水包圍
UnionFind uf = new UnionFind(size + 1);
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (grid[i][j] == '1') {
for (int[] direction : directions) {
int newX = i + direction[0];
int newY = j + direction[1];
if (newX < r && newY < c && grid[newX][newY] == '1') {
uf.union(c * i + j, c * newX + newY);
}
}
} else {
// 如果不是陸地，則所有水域與虛擬水域連接
uf.union(c * i + j, size);
}
}
}
// 減去虛擬水域
return uf.count() - 1;
}
}
等式方程的可滿足性
題目描述如下：
給定一個由表示變數之間關係的字元串方程組成的數組，每個字元串方程
equations[i]的長度為 4，並採用兩種不同形式之一：a==b或a!=b。在這裡，a 和 b 是小寫字母（不一定不同），表示單字母變數名。只有當可以將整數分配給變數名，以便滿足所有給定的方程時才返回
true，否則返回false。 輸入輸出示例如下：輸入：[“a == b”, “b == c”, “a == c”]
輸出：true輸入：[“a == b”, “b != c”, “c == a”]
輸出：false
採用並查集演算法解決該問題，如下：
class Solution {
public boolean equationsPossible(String[] equations) {
// 可能出現的26個字母
UnionFind uf = new UnionFind(26);
// 將相等的字母進行連接
for (String e : equations) {
if (e.charAt(1) == '=') {
char x = e.charAt(0);
char y = e.charAt(3);
uf.union(x - 'a', y - 'a');
}
}
// 若已經成立的相等關係被打破就返回false
for (String e : equations) {
if (e.charAt(1) == '!') {
char x = e.charAt(0);
char y = e.charAt(3);
if (uf.connected(x - 'a', y - 'a')) return false;
}
}
return true;
}
}
Union-Find演算法的簡單總結
並查集演算法主要是解決圖中的動態連通性問題。對於類似島嶼數量的問題，注意在初始化並查集時做到+1來表示一個虛擬節點，同時對於其中的二維數組可以採用方向數組int[] directions = {{1, 0}, {0, 1}}來規範和簡化程式碼。對於等式方程的可滿足性，主要是利用了並查集演算法的等價特點。
參考
labuladong在leetcode547的題解
