高效处理集合合并与查询：Python并查集（Union-Find）数据结构详解

基础实现：数组表示法

最简单的并查集可以用一个数组 parent 表示，其中 parent[i] 存储元素 i 的父节点。初始时，每个元素都是自己的父节点，即独立集合。

class UnionFind:    def __init__(self, n):        # 初始化：每个元素的父节点是自己        self.parent = list(range(n))        def find(self, x):        # 查找 x 的根节点        if self.parent[x] != x:            return self.find(self.parent[x])        return x        def union(self, x, y):        # 合并 x 和 y 所在的集合        root_x = self.find(x)        root_y = self.find(y)        if root_x != root_y:            self.parent[root_x] = root_y  

这个基础版本虽然简单，但效率不高。例如，在一条链式结构中，find 操作可能需要 O(n) 时间。

优化一：路径压缩（Path Compression）

路径压缩是在 find 操作时，将查找路径上的所有节点直接连接到根节点，从而“压扁”树的高度。

    def find(self, x):        if self.parent[x] != x:            # 递归查找根，并将当前节点直接指向根            self.parent[x] = self.find(self.parent[x])        return self.parent[x]  

优化二：按秩合并（Union by Rank）

“秩”可以理解为树的高度。合并时，总是将秩小的树接到秩大的树下，避免树变得过高。

class UnionFind:    def __init__(self, n):        self.parent = list(range(n))        self.rank = [0] * n  # 初始秩为0        def find(self, x):        if self.parent[x] != x:            self.parent[x] = self.find(self.parent[x])        return self.parent[x]        def union(self, x, y):        root_x = self.find(x)        root_y = self.find(y)        if root_x == root_y:            return  # 已在同一集合                # 按秩合并        if self.rank[root_x] < self.rank[root_y]:            self.parent[root_x] = root_y        elif self.rank[root_x] > self.rank[root_y]:            self.parent[root_y] = root_x        else:            self.parent[root_y] = root_x            self.rank[root_x] += 1  # 秩相等时，新根秩+1  

使用示例

下面是一个完整使用案例，判断图中是否存在环：

# 创建包含5个节点的并查集uf = UnionFind(5)# 添加边 (0,1), (1,2), (3,4)uf.union(0, 1)uf.union(1, 2)uf.union(3, 4)# 查询连通性print(uf.find(0) == uf.find(2))  # Trueprint(uf.find(0) == uf.find(3))  # False# 再添加边 (2,3)，此时整个图连通uf.union(2, 3)print(uf.find(0) == uf.find(4))  # True  

总结

通过本教程，你已经掌握了Python并查集的核心概念与实现方法。结合路径压缩和按秩合并，并查集的操作接近常数时间复杂度（阿克曼函数的反函数），极其高效。

无论是解决并查集数据结构相关面试题，还是实现图算法如Kruskal，这个工具都不可或缺。希望这篇Python数据结构教程能助你在编程之路上更进一步！

提示：实际项目中可使用 networkx 等库，但理解底层原理对提升算法能力至关重要。