Union Find 算法
- Union Find 算法介绍
- Union Find 算法应用
1. Union Find 算法介绍
Union Find 算法，也就是常说的并查集算法，主要是解决图论中「动态连通性」问题的。
动态连通性可以抽象成给一幅图连线，比如下面这幅图，总共有 10 个节点，它们互不相连，分别用 0~9 标记：
而 Union-Find 算法主要是实现以下 API：
class UnionFind {
// 将 p 和 q 连接
public void union(int p, int q);
// 判断 p 和 q 是否连通
public boolean connected(int p, int q);
// 返回图中有多少个连通分量
public int count();
}
这里的「连通」是一种等价关系，具有如下性质：
- 自反性：节点 p 和 p 是连通的。
- 对称性：如果节点 p 和 q 连通，那么 q 和 p 也连通。
- 传递性：如果节点 p 和 q 连通，q 和 r 连通，那么 p 和 r 也连通。
比如上面图中，0~9 任意两个不同的点都不连通，调用 connected 都会返回 false，连通分量为 count = 10 个。
如果现在调用 union(0, 1)，那么 0 和 1 被连通，连通分量降为 9 个。
再调用 union(1, 2)，这时 0,1,2 都被连通，调用connected(0, 2) 也会返回 true，连通分量变为 8 个。
Union Find 算法的关键就在于 union 和 connected 函数的效率。
接下来使用森林（若干棵树）来表示图的动态连通性，用数组来具体实现这个森林。代码实现如下：
public class UnionFind {
private int count; // 记录连通分量
private int[] parent; // 节点 x 的节点是 parent[x]
/**
* 构造函数，n 为图的节点总数
*/
public UnionFind(int n) {
// 一开始互不连通
this.count = n;
// 父节点指针初始指向自己
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
/**
* 将 p 和 q 连接
*
* 如果某两个节点被连通，则让其中的（任意）一个节点的根节点接到另一个节点的根节点上
*/
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
// 将两棵树合并为一棵
parent[rootP] = rootQ; // parent[rootQ] = rootP 也一样
count--;// 两个分量合二为一
}
/**
* 判断 p 和 q 是否连通
*/
public boolean connected(int p, int q) {
// 如果节点 p 和 q 连通的话，它们一定拥有相同的根节点
return find(p) == find(q);
}
/**
* 返回图中有多少个连通分量
*/
public int count() {
return count;
}
/**
* 返回某个节点 x 的根节点
*/
private int find(int x) {
// 根节点的 parent[x] == x
while (parent[x] != x) {
x = parent[x];
}
return x;
}
}
上面算法中，connected 和 union 中的复杂度都是 find 函数造成的，即它们的复杂度和 find 一样。
而 find 主要功能就是从某个节点向上遍历到树根，其时间复杂度是 O(N)。
注：logN 的高度只存在于平衡二叉树，显示上面的树容易出现极端不平衡的情况，使得「树」几乎退化成「链表」，使得树的高度最坏情况下变成 N。
优化平衡性可从 union 入手，把小一些的树接到大一些的树下面，这样就能避免头重脚轻，更平衡一些。额外使用一个 size 数组，记录每棵树包含的节点数如下：
private int[] size; // 新增一个数组记录树的“重量”
/**
* 构造函数，n 为图的节点总数
*/
public UnionFind(int n) {
...
// 最初每棵树只有一个节点，重量应该初始化 1
size = new int[n];
for (int i = 0; i < n; i++) {
...
size[i] = 1;
}
}
/**
* 将 p 和 q 连接
*/
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
// 将两棵树合并为一棵
//parent[rootP] = rootQ; // parent[rootQ] = rootP 也一样
// 小树接到大树下面，较平衡
if (size[rootP] > size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
} else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
count--;// 两个分量合二为一
}
这样，find，union，connected 的时间复杂度都下降为 O(logN)。
当然还可以进一步压缩每棵树的高度，使树高始终保存为常数，从 find 方法入手：
private int find(int x) {
while (parent[x] != x) {
// 进行路径压缩
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
这样 find 就能以 O(1) 的时间找到某一节点的根节点，相应的，connected 和 union 复杂度都下降为 O(1)。
完整代码如下：
/**
* 构造函数初始化数据结构需要 O(N) 的时间和空间复杂度；
* 连通两个节点union、判断两个节点的连通性connected、计算连通分量count所需的时间复杂度均为 O(1)
*/
public class UnionFind {
private int count; // 记录连通分量
private int[] parent; // 节点 x 的节点是 parent[x]
private int[] size; // 新增一个数组记录树的“重量”
/**
* 构造函数，n 为图的节点总数
*/
public UnionFind(int n) {
// 一开始互不连通
this.count = n;
// 父节点指针初始指向自己
parent = new int[n];
// 最初每棵树只有一个节点，重量应该初始化 1
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
/**
* 将 p 和 q 连接
*/
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
// 将两棵树合并为一棵
//parent[rootP] = rootQ; // parent[rootQ] = rootP 也一样
// 小树接到大树下面，较平衡
if (size[rootP] > size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
} else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
count--;// 两个分量合二为一
}
/**
* 判断 p 和 q 是否连通
*/
public boolean connected(int p, int q) {
// 如果节点 p 和 q 连通的话，它们一定拥有相同的根节点
return find(p) == find(q);
}
/**
* 返回图中有多少个连通分量
*/
public int count() {
return count;
}
/**
* 返回某个节点 x 的根节点
*/
private int find(int x) {
// 根节点的 parent[x] == x
while (parent[x] != x) {
// 进行路径压缩
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}
小结：
1、用 parent 数组记录每个节点的父节点，相当于指向父节点的指针，所以 parent 数组内实际存储着一个森林（若干棵多叉树）。
2、用 size 数组记录着每棵树的重量，目的是让 union 后树依然拥有平衡性，而不会退化成链表，影响操作效率。
3、在 find 函数中进行路径压缩，保证任意树的高度保持在常数，使得 union 和 connected 时间复杂度为 O(1)。
2. Union Find 算法应用
力扣 990 题如下：
上题中，如果 equations 中所有算式都不会互相冲突，返回 true，否则返回 false。
前面提到，动态连通性其实就是一种等价关系，具有自反性、传递性和对称性，而 == 关系也是一种等价关系，具有这些性质。因此可用 Union Find 算法 来实现，代码如下：
/**
* 判定合法算式
* <p>
* 将 equations 中的算式根据 == 和 != 分成两部分，先处理 == 算式，使得它们通过相等关系各自勾结成门派；
* 然后处理 != 算式，检查不等关系是否破坏了相等关系的连通性。
*/
boolean equationPossible(String[] equations) {
// 26 个英文字母
UnionFind uf = new UnionFind(26);
// 先让相等的字母形成连通分量
for (String eq : equations) {
if (eq.charAt(1) == '=') {
char x = eq.charAt(0);
char y = eq.charAt(3);
uf.union(x - 'a', y - 'a');
}
}
// 检查不等关系是否打破相等关系的连通性
for (String eq : equations) {
if (eq.charAt(1) == '!') {
char x = eq.charAt(0);
char y = eq.charAt(3);
// 如果相等关系成立，就是逻辑冲突
if (uf.connected(x - 'a', y - 'a')) {
return false;
}
}
}
return true;
}
总结：使用 Union Find 算法，主要是如何把原问题转化成图的动态连通性问题。对于算式合法性问题，可以直接利用等价关系，营造出动态连通特性。
参考链接：
