一、动态连通性
图的节点是否连通的问题，用下面两个图很好表示：
A, B, C, D 都是连通的，FG 连通， FH 却不连通。
并查集的数据结构就是为了快速判断图中两个节点（子图）是否连通。并查集 Union-Find 算法主要实现这两个API
1
2
3
4
5
6
7
8
|
class UF {
/* 将 p 和 q 连接 */
public void union(int p, int q);
/* 判断 p 和 q 是否连通 */
public boolean connected(int p, int q);
/* 返回图中有多少个连通分量 */
public int count();
}
|
二、基本思路
注意我刚才把「模型」和具体的「数据结构」分开说，这么做是有原因的。因为我们使用森林（若干棵树）来表示图的动态连通性，用数组来具体实现这个森林。
怎么用森林来表示连通性呢？我们设定树的每个节点有一个指针指向其父节点，如果是根节点的话，这个指针指向自己。比如说刚才那幅 10 个节点的图，一开始的时候没有相互连通，就是这样：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class UF {
// 记录连通分量
private int count;
// 节点 x 的节点是 parent[x]
private int[] parent;
/* 构造函数，n 为图的节点总数 */
public UF(int n) {
// 一开始互不连通
this.count = n;
// 父节点指针初始指向自己
parent = new int[n];
for (int i = 0; i < n; i++)
parent[i] = i;
}
/* 其他函数 */
}
|
如果某两个节点被连通，则让其中的（任意）一个节点的根节点接到另一个节点的根节点上
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
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--; // 两个分量合二为一
}
/* 返回某个节点 x 的根节点 */
private int find(int x) {
// 根节点的 parent[x] == x
while (parent[x] != x)
x = parent[x];
return x;
}
/* 返回当前的连通分量个数 */
public int count() {
return count;
}
|
这样，如果节点 p 和 q 连通的话，它们一定拥有相同的根节点
1
2
3
4
5
|
public boolean connected(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
return rootP == rootQ;
}
|
并查集的数据结构实现并不难，主要是记录节点的根节点，并用数组实现，但是目前还有很多优化的地方。
三、最终优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
class UF {
// 连通分量个数
private int count;
// 存储一棵树
private int[] parent;
// 记录树的「重量」
private int[] size;
// n 为图中节点的个数
public UF(int n) {
this.count = n;
parent = new int[n];
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;
// 小树接到大树下面，较平衡
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) {
int rootP = find(p);
int rootQ = find(q);
return rootP == rootQ;
}
// 返回节点 x 的连通分量根节点
private int find(int x) {
while (parent[x] != x) {
// 进行路径压缩
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
// 返回图中的连通分量个数
public int count() {
return count;
}
}
|
- 利用size 数组记录每棵树的节点个数，节点数少的合并到多的树上。
- 改变find 函数，将树摊平。
四、应用
130. 被围绕的区域（中等）
990. 等式方程的可满足性（中等）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
UF uf = new UF(n);
int[] res = null;
for (int i = 0; i < n; i++) {
int ai = edges[i][0], bi = edges[i][1];
if (uf.connected(ai-1, bi-1)) {
res = new int[]{ai, bi};
}
uf.union(ai-1, bi-1);
}
return res;
}
}
|