第 42 课·图算法进阶

并查集

union-finddisjoint-setpath-compressionrank

第 42 课 - 并查集 (Union-Find)

所属模块：图算法
难度：Intermediate
标签：union-find, disjoint-set, path-compression, rank
上一课：拓扑排序
下一课：Dijkstra 最短路径

1. 学习目标

通过本课的学习，你将能够：

  1. 理解并查集的基本概念和应用场景：知道什么是并查集，以及它如何高效地管理“不相交集合”。
  2. 掌握并查集的两种核心优化方法：实现“路径压缩”和“按秩合并”，将操作时间复杂度从线性降低到接近常数级别。
  3. 应用并查集解决实际问题：能够使用并查集解决图论中的连通性问题、动态连接性问题等经典问题。

2. 核心概念

什么是并查集？

想象一下，我们有一群学生，他们最初各自独立。现在，我们开始让他们加入不同的社团（例如“编程社”、“篮球社”）。并查集就像一个社团管理器，它能高效地处理两个核心操作：

  1. Find (查找)：快速确定一个学生属于哪个社团。
  2. Union (合并)：将两个不同的社团合并成一个更大的社团。

在数据结构术语中：

  • 每个元素最初属于一个独立的集合（一个元素一个集合）。
  • Find(x) 操作返回 x 所在集合的“代表元素”（通常是根节点）。
  • Union(x, y) 操作将 x 和 y 所在的两个集合合并为一个。

数据结构表示：森林

并查集通常用一个“森林”（多棵树）来表示，每棵树对应一个集合，树的根节点就是该集合的代表元素。

  • 我们用一个数组 parent 来存储每个节点的父节点。如果 parent[i] == i，则说明 i 是其所在树的根节点（代表元素）。

核心优化：让树更“扁平”

朴素实现中，树可能会变得很深，导致 Find 操作退化为 O(n)。我们通过两个技巧来优化：

  1. 路径压缩 (Path Compression)：

    • 在做什么：在执行 Find(x) 的过程中，不仅找到根节点，还将路径上所有节点的父节点直接指向根节点。
    • 效果：下次再查找这些节点时，就能一步到位，大大扁平化了树结构。
    • 类比：你去社团办公室问社长是谁。社长告诉你后，你记住了“这个社团的社长就是张三”，下次你或你的朋友再问，就直接知道了。

  2. 按秩合并 (Union by Rank)：

    • 在做什么：在合并两棵树时，总是将“矮树”（秩小）的根节点，连接到“高树”（秩大）的根节点下。
    • 效果：避免树退化成一条长长的链，保持树的高度较低。
    • 类比：合并社团时，让成员少的小社团并入成员多的大社团，而不是反过来。

时间复杂度：结合了这两种优化后，Find 和 Union 操作的摊还时间复杂度几乎为 O(α(n))，其中 α 是一个增长极其缓慢的阿克曼函数的反函数，对于现实中的任何 n，α(n) 都可以视为一个不超过 5 的常数。因此，实际效率非常高。

3. 代码示例

下面是一个完整的并查集实现，包含了路径压缩和按秩合并。

class UnionFind:
    def __init__(self, n):
        """
        初始化并查集
        :param n: 元素的个数（通常元素编号从0到n-1）
        """
        # parent[i] 表示元素 i 的父节点
        self.parent = list(range(n))
        # rank[i] 表示以 i 为根的树的“秩”（可以理解为树高度的上界）
        self.rank = [0] * n
        # count 记录当前集合（连通分量）的数量
        self.count = n

    def find(self, x):
        """
        查找元素 x 所在集合的代表元素（根节点），并进行路径压缩
        :param x: 要查找的元素
        :return: 根节点
        """
        # 如果 x 不是根节点，递归查找并压缩路径
        if self.parent[x] != x:
            # 路径压缩：在递归回来时，将路径上所有节点的父节点直接设为根节点
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        """
        合并元素 x 和 y 所在的集合（按秩合并）
        :param x: 元素 x
        :param y: 元素 y
        :return: 如果合并成功（原本不在同一集合）返回 True，否则返回 False
        """
        root_x = self.find(x)
        root_y = self.find(y)

        # 如果已经在同一个集合，无需合并
        if root_x == root_y:
            return False

        # 按秩合并：将秩小的树合并到秩大的树下
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x  # 交换，确保 root_x 是秩较大的根

        # 将 root_y 的根指向 root_x
        self.parent[root_y] = root_x

        # 如果两棵树秩相同，合并后树的高度（秩）加 1
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1

        # 合并后，连通分量数量减 1
        self.count -= 1
        return True

    def connected(self, x, y):
        """
        检查元素 x 和 y 是否在同一个集合（是否连通）
        :return: 布尔值
        """
        return self.find(x) == self.find(y)

# 使用示例
if __name__ == "__main__":
    # 创建一个包含 5 个元素的并查集 (0,1,2,3,4)
    uf = UnionFind(5)

    # 初始时，有 5 个独立的集合
    print(f"初始集合数量: {uf.count}")  # 输出: 5

    # 合并 0 和 1
    uf.union(0, 1)
    print(f"合并 (0,1) 后集合数量: {uf.count}")  # 输出: 4
    print(f"0 和 1 连通吗? {uf.connected(0, 1)}")  # 输出: True

    # 合并 2 和 3
    uf.union(2, 3)
    print(f"合并 (2,3) 后集合数量: {uf.count}")  # 输出: 3

    # 合并 1 和 3，这会将 {0,1} 和 {2,3} 两个集合合并
    uf.union(1, 3)
    print(f"合并 (1,3) 后集合数量: {uf.count}")  # 输出: 2
    print(f"0 和 3 连通吗? {uf.connected(0, 3)}")  # 输出: True

    # 查找某个元素的根
    print(f"元素 0 的根是: {uf.find(0)}")
    print(f"元素 4 的根是: {uf.find(4)}")

代码输出：

初始集合数量: 5
合并 (0,1) 后集合数量: 4
0 和 1 连通吗? True
合并 (2,3) 后集合数量: 3
合并 (1,3) 后集合数量: 2
0 和 3 连通吗? True
元素 0 的根是: 0
元素 4 的根是: 4

4. 实践练习

练习 1：基础连通性判断

给定一个初始有 n 个节点的图和一系列边 edges，使用并查集判断图是否全连通（即所有节点都在同一个集合中）。

  • 输入: n = 5, edges = [[0,1], [1,2], [3,4]]
  • 输出: False（因为节点 0,1,2 和节点 3,4 不连通）
  • 提示: 遍历所有边进行合并，最后检查并查集的 count 是否为 1。

练习 2：冗余连接（中等）

在图中找到一条可以删除的边，使得图从一棵树变成有根树。换句话说，找到最后一条导致图中出现环的边。

  • 输入: edges = [[1,2], [1,3], [2,3]]
  • 输出: [2,3]
  • 提示: 依次处理每条边。如果一条边的两个端点在合并前已经连通，那么这条边就是冗余的（会形成环）。

练习 3：岛屿数量（进阶）

给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

  • 输入: 
    grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
  • 输出: 3
  • 提示: 将二维网格扁平化为一维索引 (index = row * num_cols + col)。遍历网格，当遇到陆地('1')时，尝试将其与上边和左边的陆地进行合并。最终并查集中根节点的数量（或者连通分量数）就是岛屿数量。

5. 常见错误

  1. 忘记路径压缩：

    • 错误：Find 函数只查找根节点，但不更新路径上节点的父节点。
    • 后果：树的高度可能持续增长，导致后续操作变慢。
    • 正确做法：在 Find 递归返回时，执行 self.parent[x] = self.find(self.parent[x])。

  2. 忽略按秩合并：

    • 错误：合并时总是简单地将一个根节点指向另一个，不考虑树的高度。
    • 后果：可能将高树合并到矮树下，增加不必要的树高。
    • 正确做法：维护 rank 数组，比较秩大小，将小秩树合并到大秩树下。

  3. 合并时未找到根节点：

    • 错误：Union(x, y) 操作直接合并 x 和 y，而不是它们的根节点。
    • 后果：破坏树结构，导致后续 Find 操作出错。
    • 正确做法：合并前必须先调用 find(x) 和 find(y) 获取各自的根节点。

  4. 初始化错误：

    • 错误：将 parent 数组初始化为 -1 或其他无效值，但 Find 函数未正确处理。
    • 正确做法：通常将 parent[i] 初始化为 i，表示每个节点最初是自己的父节点（根节点）。

6. 小结

  • 并查集是什么：一种高效管理不相交集合（Disjoint Sets）的数据结构，专门优化了集合合并和元素所属查询两个操作。
  • 核心操作：
    • Find(x): 查找 x 的根节点（代表元素）。
    • Union(x, y): 合并 x 和 y 所在的集合。
  • 关键优化：
    • 路径压缩：在 Find 过程中扁平化树结构，使后续查询更快。
    • 按秩合并：在 Union 过程中优先将矮树并入高树，保持树的平衡。
  • 应用场景：主要用于解决动态连通性问题，例如：
    • 判断图中两个节点是否连通。
    • 计算图中的连通分量数量（如岛屿问题）。
    • 检测图中是否存在环。
    • Kruskal 最小生成树算法（用于判断加入的边是否形成环）。
  • 性能：经过双重优化后，单次操作的摊还时间复杂度接近 O(1)，非常高效。

并查集的思想简洁而强大，是解决许多图论和集合论问题的基石。掌握它将为你后续学习更复杂的图算法（如 Kruskal）打下坚实基础。

练习编辑器

rust
Loading...

继续学习

完成本课后，建议继续学习下一课「Dijkstra 最短路径」 以巩固所学知识。