动态连通性

![[第二单元 并查.png]]

对于动态连通性问题，有两种操作：

1. 合并：把两个元素合并为一个集合中
2. 检查：判断两个元素是否连通（属于同一个集合）

有了并查集，就可以高效地解决路径寻找问题。

问题建模

对于每个元素进行建模：把每个元素映射到 0 到 N-1 的序列，以此来编号。

对于连接进行建模：连接是一个等价关系，具有三个性质：

• 自反性：p 本身连接到 p。
• 对称性：p 连接到 q ，那么 q 连接到 p。
• 传递性：p 连接到 q，q 连接到 r，那么 p 连接到 r。

连通分量是相互连接的元素的最大集合。

![[第二单元 并查-1.png]]

并查集 ADT

public interface UF() {
	// 连接 p 和 q
	void union(int p, int q) {
	}
	
	// 检查p 和 q 是否连通
	boolean connected(int p, int q) {
	}
}

实现方法一：快速查找

![[quick_find.png]]

• Connected：检查 id[p] 和 id[q]是否相等。
• Union：将所有的 q 的 id 改成 id[p]。

时间复杂度：

• 初始化：O(N)
• Connected：O(1)
• Union：O(N)

可以看出合并的时间复杂度挺大的，特别是对 N 个元素进行 N 次操作的时候，复杂度高达 O(N)。对于大型问题，我们不能接受二次方的时间复杂度。因此快速查找这样的实现不够好。

实现方法二：快速合并

![[quick_union.png]]

与快速查找不同，快速合并的 id 数组存储的是该节点的父节点的 id。

当一个节点没有父节点，这个节点就称为根（root）

• Connected：检查 p 和 q 的 root 是否相等。
• Union：将所有的 q 的 root 的值改为 p 的 root。

时间复杂度：

• 初始化：O(N)
• Connected：O(N)（还需要遍历树以查找根）
• Union：O(N)

快速合并这样的实现有时候很快，但是如果树是一颗很高的树，最差情况就会很慢。

所以接下来我们要想方设法制造一颗矮一点的树。

实现方法三：加权快速合并

![[weighted_quick_union.png]]

由上图可知，让高的树作为矮的树的根，可以使整个树的高度小一些。同样的，让元素多的树作为元素少的树的根，也可以达成这个目的。这分别称为 weight by height 和 weight by size。

![[Pasted image 20250606162016.png]]

实现该算法，需要在快速合并算法的基础上新建一个 size 列表，存储该元素所在树的元素个数，每次合并的时候对两颗树进行比较，这样才能把大的树作为根。

这样的算法可以使得树的高度接近 lgN。

时间复杂度：

• 初始化：O(N)
• Connected：O(lgN)
• Union：O(lgN)

这样的时间复杂度就好多了。

实现方法四：带路径压缩的加权快速合并

加权快速合并还有个问题：在寻找指定节点的根节点的时候需要从该节点遍历整棵树，造成较大的复杂度。

因此我们可以在查找 root 的操作之后，直接将该节点与根节点连接起来，这样可以把树展平，疯狂地降低树的高度！

总结

动态连通性可以采用并查集解决。在实际应用中通常采用带路径压缩的加权快速合并算法，其时间复杂度更接近线性。

目前科学家已经证明了动态连接性问题不存在线性复杂度的算法。