数据结构与算法 / 系统课时
并查集与集合连通性
并查集与集合连通性
并查集用于回答“两个元素是否属于同一集合”,并支持不断合并集合。它不保存两点之间的具体路径,而是通过父节点森林、路径压缩和按秩合并,把大量动态连通查询的均摊成本降到接近常数。
学习目标
- 理解父节点森林和集合代表元的含义
- 实现路径压缩、按秩合并与连通性判断
- 使用并查集识别无向图中的冗余边
数据结构与关键优化
初始化时,每个元素各自形成一个集合,父节点指向自身。find(x) 沿父指针找到根节点,这个根就是集合的代表元;两个元素的代表元相同,就属于同一集合。
union(a, b) 不能直接连接普通节点,而要先分别查找两个根。若根相同,说明已经连通;若根不同,再把一棵树的根挂到另一棵树的根下。

路径压缩在 find 返回根节点时,把查找路径上的节点直接连接到根。之后再次查询这些节点时,通常只需一两步。
按秩合并使用 rank 近似记录树高。合并时把低秩树挂到高秩树下;只有两棵树秩相同,合并后的根秩才加一。路径压缩会改变实际树高,因此不能在压缩过程中随意修改 rank。
两种优化结合后,连续 次操作的复杂度为 ,其中 是反阿克曼函数,在实际数据规模下可视为非常小的常数。空间复杂度为 。
主示例:检测冗余边
下面依次加入无向边。当某条边的两个端点已经连通时,再加入它就会形成环,因此该边是当前输入中的冗余边。
python
class UnionFind:
def __init__(self, size):
if size < 0:
raise ValueError("size must be non-negative")
self.parent = list(range(size))
self.rank = [0] * size
self.component_count = size
def find(self, value):
if not 0 <= value < len(self.parent):
raise IndexError("value is out of range")
# 递归返回时把整条查找路径直接连接到根节点。
if self.parent[value] != value:
self.parent[value] = self.find(self.parent[value])
return self.parent[value]
def union(self, first, second):
root_first = self.find(first)
root_second = self.find(second)
if root_first == root_second:
return False
# 低秩树挂到高秩树下,避免父节点森林退化成链。
if self.rank[root_first] < self.rank[root_second]:
root_first, root_second = root_second, root_first
self.parent[root_second] = root_first
if self.rank[root_first] == self.rank[root_second]:
self.rank[root_first] += 1
self.component_count -= 1
return True
def connected(self, first, second):
return self.find(first) == self.find(second)
edges = [(0, 1), (1, 2), (3, 4), (2, 4), (0, 4)]
uf = UnionFind(6)
redundant_edges = []
for first, second in edges:
if not uf.union(first, second):
redundant_edges.append((first, second))
print("冗余边:", redundant_edges)
print("0 与 4 连通:", uf.connected(0, 4))
print("0 与 5 连通:", uf.connected(0, 5))
print("集合数量:", uf.component_count)
print("父节点数组:", uf.parent)预期输出:
text
冗余边: [(0, 4)]
0 与 4 连通: True
0 与 5 连通: False
集合数量: 2
父节点数组: [0, 0, 0, 0, 0, 5]最后一行的父节点数组是当前内部状态,不是稳定的业务输出;后续执行更多 find 可能继续压缩路径,但不会改变连通关系。
适用范围与限制
并查集适合处理只增加连接、不删除连接的动态连通问题,例如账户合并、网络连通、最小生成树和环检测。它能快速判断是否连通,却不会直接给出两点之间经过哪些边。
标准并查集不擅长在线删除边。删除可能把一个集合拆成多个集合,需要离线逆序处理、可回滚并查集或其他动态图结构。
按自己的节奏,确认真正理解。