并查集
- 理解并查集的定义及其作用。
- 掌握并查集的基本操作，包括查找（Find）和合并（Union）。
- 学习并查集的两种优化策略：按秩合并（Union by Rank）和路径压缩（Path Compression）。
- 能够编写并查集的代码实现。
教学内容
1. 并查集的定义及作用
定义
并查集是一种数据结构，用于管理一组不相交的集合。它支持两种操作：
- 查找（Find）：确定元素属于哪个集合。
- 合并（Union）：将两个集合合并为一个集合。
并查集常用于处理连通性问题，例如判断图中两个节点是否在同一个连通分量中。
作用
并查集广泛应用于以下场景：
- 动态连通性问题：在网络中快速判断节点是否连通。
- Kruskal算法：用于求解最小生成树。
- 检测无向图中的环。
2. 并查集的基本操作
初始化
每个元素开始时都是一个单独的集合，可以用一个数组表示，每个元素的父节点初始化为它自己。
1
2
3
| class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
|
查找（Find）
查找操作用于找到某个元素所属集合的根节点。
1
2
3
4
| def find(self, p):
while p != self.parent[p]:
p = self.parent[p]
return p
|
合并（Union）
合并操作将两个元素所在的集合合并。
1
2
3
4
5
| def union(self, p, q):
rootP = self.find(p)
rootQ = self.find(q)
if rootP != rootQ:
self.parent[rootP] = rootQ
|
3. 并查集的优化
按秩合并（Union by Rank）
按秩合并是一种优化策略，通过维护树的高度（或秩），总是将秩小的树合并到秩大的树上，从而避免树变得过高。
秩的初始化
需要增加一个数组来维护每个集合的秩。
1
2
3
4
| class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [0] * size
|
按秩合并的实现
在合并操作中，比较两个根节点的秩，将秩小的树合并到秩大的树上。如果两个根节点的秩相同，则合并后增加新的根节点的秩。
1
2
3
4
5
6
7
8
9
10
11
| def union(self, p, q):
rootP = self.find(p)
rootQ = self.find(q)
if rootP != rootQ:
if self.rank[rootP] < self.rank[rootQ]:
self.parent[rootP] = rootQ
elif self.rank[rootP] > self.rank[rootQ]:
self.parent[rootQ] = rootP
else:
self.parent[rootQ] = rootP
self.rank[rootP] += 1
|
路径压缩（Path Compression）
路径压缩是一种优化查找操作的方法，通过将查找路径上的所有节点直接连接到根节点，从而加速后续的查找操作。
路径压缩的实现
在查找操作中，递归地将每个节点直接连接到根节点。
1
2
3
4
| def find(self, p):
if p != self.parent[p]:
self.parent[p] = self.find(self.parent[p])
return self.parent[p]
|
4. 完整的并查集实现
将上述优化策略结合起来，得到完整的并查集实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [0] * size
def find(self, p):
if p != self.parent[p]:
self.parent[p] = self.find(self.parent[p])
return self.parent[p]
def union(self, p, q):
rootP = self.find(p)
rootQ = self.find(q)
if rootP != rootQ:
if self.rank[rootP] < self.rank[rootQ]:
self.parent[rootP] = rootQ
elif self.rank[rootP] > self.rank[rootQ]:
self.parent[rootQ] = rootP
else:
self.parent[rootQ] = rootP
self.rank[rootP] += 1
|
5. 例子及练习
例子
1
2
3
4
5
6
7
| uf = UnionFind(10)
uf.union(1, 2)
uf.union(2, 3)
print(uf.find(1))
print(uf.find(2))
print(uf.find(3))
print(uf.find(4))
|
练习
- 编写代码验证并查集是否正确处理动态连通性。
- 使用并查集解决图中的连通分量问题。
- 通过路径压缩和按秩合并优化验证并查集性能提升。
6. 总结
并查集是一种高效处理动态连通性问题的数据结构，通过路径压缩和按秩合并优化，可以显著提升其性能。通过理解并掌握并查集的基本操作及优化策略，能够有效解决许多实际问题。
7. 参考资料
