并查集

本文来自Coursera的Algorithms, Part I课程

动态连通性

我们假设“相连”是一种等价关系,这也就意味 着它具有:

  • 自反性:p 和 p 是相连的
  • 对称性:如果 p 和 q 是相连的,那么 q 和 p 也是相连的
  • 传递性:如果 p 和 q 是相连的且 q 和 r 是相连的,那么 p 和 r 也是相连的

连通分量

连通分量是相连元素组成的最大集合

查找

检查两个元素是否在一个分量中

归并

将两个分量归并到相同的分量中

并查集算法的API

public class UF
UF(int N) 以整数标识( 0 到 N1N-1 )初始化 NN 个触点
void union(int p, int q) 在 p 和 q 之间添加一条连接
int find(int p) p(0 到 N1N-1 )所在的分量的标识符
boolean connected(int p, int q) 如果 p 和 q 存在于同一个分量中则返回 true
int count() 连通分量的数量

quick-find 算法

数据结构

  • 长度为 N 的整型数组 id[]
  • 当且仅当 p 和 q 有相同 id 时 p 和 q 连通
1
2
3
4
5
6
private int[] id;
public QuickFindUF(int N) {
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
}

find()

返回根节点

1
2
3
public int root(int p) {
return id[p];
}

union()

把要归并的所有连通分量的 id 改为另一个连通分量的 id

1
2
3
4
5
6
public void union(int p, int q) {
int pid = id[p];
int qid = id[q];
for (int i = 0; i < id.length; i++)
if (id[i] == pid) id[i] = qid;
}

复杂度分析

算法 构造函数 union() find()
quick-find NN NN 11

union操作过于复杂,很难运用于大型问题

quick-union 算法

数据结构

还是 id[] 数组,不过这次不用把所有的分量都改了,一种“偷懒”算法,即尽量避免计算直到不得不进行计算

1
2
3
4
5
private int[] id;
public QuickUnionUF(int N) {
id = new int[N];
for (int i = 0; i < N; i++) id[i] = i;
}

find()

返回根节点

1
2
3
4
private int find(int i) {
while (i != id[i]) i = id[i];
return i;
}

union()

把要归并的连通分量的根节点的 id 改为另一个连通分量根节点的 id

1
2
3
4
5
public void union(int p, int q){
int i = find(p);
int j = find(q);
id[i] = j;
}

复杂度分析

算法 构造函数 union() find()
quick-union NN NN(包括查找根节点,取决于树的高度) NN(取决于树的高度)

union操作过于复杂,很难运用于大型问题

改进

加权 quick-union 算法

就是将小树连接到大树来降低高度

我们需要一个额外的数组 sz[] 来记录以 i 为根节点的树的大小,只要在 union 方法中加入三行:

1
2
3
4
5
6
7
8
9
10
11
12
public void union(int p, int q){
int i = find(p);
int j = find(q);
id[i] = j;
if (i == j) return;
if (sz[i] < sz[j]) {
id[i] = j; sz[j] += sz[i];
}
else {
id[j] = i; sz[i] += sz[j];
}
}

复杂度分析

算法 构造函数 union() find()
weighted QU NN lgN\lg N(包括查找根节点) lgN\lg N

我们能不能再进一步?

使用路径压缩的加权 quick-union 算法

顾名思义,就是路径压缩(

为了简化路径压缩,直接加上一行代码就行了,将路径上每个节点指向它在路径上的祖父节点。这种实现不如完全展平好,但在实际应用中两者差不多一样好:

1
2
3
4
5
6
7
private int find(int i) {
while (i != id[i]) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}

复杂度分析

算法 构造函数 union() find()
weighted QU NN 非常接近线性 1(均摊 成本)

并查集
https://ivansnow02.github.io/posts/61809/
作者
Ivan Snow
发布于
2023年5月21日
许可协议