本文来自 Coursera 的 Algorithms, Part I 课程
# 动态连通性
# 我们假设 “相连” 是一种等价关系，这也就意味 着它具有：
- 自反性：p 和 p 是相连的
- 对称性：如果 p 和 q 是相连的，那么 q 和 p 也是相连的
- 传递性：如果 p 和 q 是相连的且 q 和 r 是相连的，那么 p 和 r 也是相连的
# 连通分量
连通分量是相连元素组成的最大集合
# 查找
检查两个元素是否在一个分量中
# 归并
将两个分量归并到相同的分量中
# 并查集算法的 API
public class UF |
|
|---|---|
UF(int N) |
以整数标识（ 0 到 ）初始化 个触点 |
void union(int p, int q) |
在 p 和 q 之间添加一条连接 |
int find(int p) |
p（0 到 ）所在的分量的标识符 |
boolean connected(int p, int q) |
如果 p 和 q 存在于同一个分量中则返回 true |
int count() |
连通分量的数量 |
# quick-find 算法
# 数据结构
- 长度为 N 的整型数组
id[] - 当且仅当 p 和 q 有相同
id时 p 和 q 连通
private int[] id; | |
public QuickFindUF(int N) { | |
id = new int[N]; | |
for (int i = 0; i < N; i++) | |
id[i] = i; | |
} |
# find()
返回根节点
public int root(int p) { | |
return id[p]; | |
} |
# union()
把要归并的所有连通分量的 id 改为另一个连通分量的 id
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 |
union 操作过于复杂，很难运用于大型问题
# quick-union 算法
# 数据结构
还是 id[] 数组，不过这次不用把所有的分量都改了，一种 “偷懒” 算法，即尽量避免计算直到不得不进行计算
private int[] id; | |
public QuickUnionUF(int N) { | |
id = new int[N]; | |
for (int i = 0; i < N; i++) id[i] = i; | |
} |
# find()
返回根节点
private int find(int i) { | |
while (i != id[i]) i = id[i]; | |
return i; | |
} |
# union()
把要归并的连通分量的根节点的 id 改为另一个连通分量根节点的 id
public void union(int p, int q){ | |
int i = find(p); | |
int j = find(q); | |
id[i] = j; | |
} |
# 复杂度分析
| 算法 | 构造函数 | union() | find() |
|---|---|---|---|
| quick-union | （包括查找根节点，取决于树的高度） | （取决于树的高度） |
union 操作过于复杂，很难运用于大型问题
# 改进
# 加权 quick-union 算法
就是将小树连接到大树来降低高度
我们需要一个额外的数组 sz[] 来记录以 i 为根节点的树的大小，只要在 union 方法中加入三行：
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 | （包括查找根节点） |
我们能不能再进一步？
# 使用路径压缩的加权 quick-union 算法
顾名思义，就是路径压缩（
为了简化路径压缩，直接加上一行代码就行了，将路径上每个节点指向它在路径上的祖父节点。这种实现不如完全展平好，但在实际应用中两者差不多一样好：
private int find(int i) { | |
while (i != id[i]) { | |
id[i] = id[id[i]]; | |
i = id[i]; | |
} | |
return i; | |
} |
# 复杂度分析
| 算法 | 构造函数 | union() | find() |
|---|---|---|---|
| weighted QU | 非常接近线性 | 1（均摊 成本） |
