数据结构与算法 / 系统课时

并查集与集合连通性

并查集与集合连通性

并查集用于回答“两个元素是否属于同一集合”,并支持不断合并集合。它不保存两点之间的具体路径,而是通过父节点森林、路径压缩和按秩合并,把大量动态连通查询的均摊成本降到接近常数。

学习目标

  • 理解父节点森林和集合代表元的含义
  • 实现路径压缩、按秩合并与连通性判断
  • 使用并查集识别无向图中的冗余边

数据结构与关键优化

初始化时,每个元素各自形成一个集合,父节点指向自身。find(x) 沿父指针找到根节点,这个根就是集合的代表元;两个元素的代表元相同,就属于同一集合。

union(a, b) 不能直接连接普通节点,而要先分别查找两个根。若根相同,说明已经连通;若根不同,再把一棵树的根挂到另一棵树的根下。

并查集路径压缩与按秩合并

路径压缩在 find 返回根节点时,把查找路径上的节点直接连接到根。之后再次查询这些节点时,通常只需一两步。

按秩合并使用 rank 近似记录树高。合并时把低秩树挂到高秩树下;只有两棵树秩相同,合并后的根秩才加一。路径压缩会改变实际树高,因此不能在压缩过程中随意修改 rank。

两种优化结合后,连续 mm 次操作的复杂度为 O(mα(n))O(m\alpha(n)),其中 α(n)\alpha(n) 是反阿克曼函数,在实际数据规模下可视为非常小的常数。空间复杂度为 O(n)O(n)。

主示例:检测冗余边

下面依次加入无向边。当某条边的两个端点已经连通时,再加入它就会形成环,因此该边是当前输入中的冗余边。

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 可能继续压缩路径,但不会改变连通关系。

适用范围与限制

并查集适合处理只增加连接、不删除连接的动态连通问题,例如账户合并、网络连通、最小生成树和环检测。它能快速判断是否连通,却不会直接给出两点之间经过哪些边。

标准并查集不擅长在线删除边。删除可能把一个集合拆成多个集合,需要离线逆序处理、可回滚并查集或其他动态图结构。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

并查集与集合连通性

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通