并查集（Union-Find）详解

1. 引言

并查集（Union-Find）是一种高效的数据结构，主要用于解决动态连通性问题。它能够快速地判断两个元素是否属于同一个集合，以及将两个不同的集合合并成一个集合。并查集在图论、网络连接、最小生成树算法（如Kruskal算法）等领域有广泛应用。

2. 基本概念

2.1 定义

并查集维护一个集合的划分，支持两种基本操作：

• Find(x)：查找元素x所在的集合（或称为查找x的根节点）
• Union(x, y)：将包含x和y的两个集合合并

2.2 核心思想

并查集通过树形结构来表示集合，每个集合由一棵树表示，树中的每个节点指向其父节点。根节点是集合的代表元素，用于标识整个集合。

3. 基础实现

3.1 数组实现

最简单的实现方式是使用数组来存储父节点信息：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # 初始化每个元素的父节点为自己
    
    def find(self, x):
        # 基础查找：递归查找根节点
        if self.parent[x] != x:
            return self.find(self.parent[x])
        return x
    
    def union(self, x, y):
        # 基础合并：将y的根节点指向x的根节点
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_y] = root_x

3.2 时间复杂度分析

基础实现的并查集在最坏情况下时间复杂度为O(n)，因为可能需要遍历整个树来找到根节点。

4. 优化技术

4.1 路径压缩（Path Compression）

路径压缩是在查找过程中将路径上的所有节点直接指向根节点，从而减少后续查找的时间：

def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])  # 递归查找并压缩路径
    return self.parent[x]

4.2 按秩合并（Union by Rank）

按秩合并是在合并时将较矮的树合并到较高的树下，保持树的高度较小：

def __init__(self, n):
    self.parent = list(range(n))
    self.rank = [0] * n  # 记录每个树的高度
    
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

4.3 按大小合并（Union by Size）

另一种优化方式是按集合大小合并，将较小的集合合并到较大的集合下：

def __init__(self, n):
    self.parent = list(range(n))
    self.size = [1] * n  # 记录每个集合的大小
    
def union(self, x, y):
    root_x = self.find(x)
    root_y = self.find(y)
    
    if root_x == root_y:
        return
    
    # 按大小合并：将较小的集合合并到较大的集合下
    if self.size[root_x] < self.size[root_y]:
        self.parent[root_x] = root_y
        self.size[root_y] += self.size[root_x]
    else:
        self.parent[root_y] = root_x
        self.size[root_x] += self.size[root_y]

5. 完整优化实现

结合路径压缩和按秩合并的并查集实现：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    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 False  # 已经在同一集合中
        
        # 按秩合并
        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
        
        return True
    
    def connected(self, x, y):
        return self.find(x) == self.find(y)

6. 时间复杂度分析

经过优化的并查集具有接近常数时间的操作：

• Find操作：O(α(n))，其中α是反阿克曼函数，增长极其缓慢
• Union操作：O(α(n))
• Connected操作：O(α(n))

对于实际应用中的n值，α(n)通常小于5，因此可以认为这些操作的时间复杂度接近O(1)。

7. 应用场景

7.1 图的连通性判断

判断无向图中两个节点是否连通：

def is_connected(graph, n):
    uf = UnionFind(n)
    
    for u, v in graph.edges:
        uf.union(u, v)
    
    return uf.connected(start_node, end_node)

7.2 最小生成树（Kruskal算法）

Kruskal算法使用并查集来检测添加边时是否形成环：

def kruskal_mst(edges, n):
    uf = UnionFind(n)
    mst = []
    edges.sort(key=lambda x: x[2])  # 按权重排序
    
    for u, v, weight in edges:
        if uf.union(u, v):
            mst.append((u, v, weight))
    
    return mst

7.3 网络连接问题

模拟网络中节点的连接和断开：

class Network:
    def __init__(self, n):
        self.uf = UnionFind(n)
    
    def connect(self, a, b):
        self.uf.union(a, b)
    
    def query(self, a, b):
        return self.uf.connected(a, b)

7.4 等价类问题

处理等价关系，将具有相同性质的元素分组：

def find_equivalence_classes(elements, relations):
    uf = UnionFind(len(elements))
    
    for a, b in relations:
        uf.union(a, b)
    
    # 获取每个元素的根节点，作为等价类的标识
    classes = {}
    for i in range(len(elements)):
        root = uf.find(i)
        if root not in classes:
            classes[root] = []
        classes[root].append(elements[i])
    
    return list(classes.values())

8. 扩展功能

8.1 路径统计

扩展并查集以支持路径统计：

class UnionFindWithPathCount:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.path_count = [1] * n  # 每个集合的节点数
    
    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 False
        
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
            self.path_count[root_y] += self.path_count[root_x]
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
            self.path_count[root_x] += self.path_count[root_y]
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
            self.path_count[root_x] += self.path_count[root_y]
        
        return True
    
    def get_size(self, x):
        return self.path_count[self.find(x)]

8.2 动态连通性

支持动态添加节点和边的并查集：

class DynamicUnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}
    
    def add(self, x):
        if x not in self.parent:
            self.parent[x] = x
            self.rank[x] = 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):
        self.add(x)
        self.add(y)
        
        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]:
            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
        
        return True

9. 性能对比

实现方式	Find时间	Union时间	空间复杂度
基础实现	O(n)	O(n)	O(n)
路径压缩	O(α(n))	O(α(n))	O(n)
按秩合并	O(α(n))	O(α(n))	O(n)
完整优化	O(α(n))	O(α(n))	O(n)

10. 优缺点分析

10.1 优点

1. 高效性：经过优化的并查集操作接近常数时间
2. 简单性：实现相对简单，易于理解和维护
3. 灵活性：可以轻松扩展以支持更多功能
4. 空间效率：只需要O(n)的额外空间

10.2 缺点

1. 不支持分割操作：无法将一个集合分割成两个集合
2. 路径压缩可能增加递归深度：在极端情况下可能导致栈溢出
3. 不适用于需要快速查找所有元素的操作：需要遍历整个集合

11. 实际应用案例

11.1 社交网络分析

class SocialNetwork:
    def __init__(self, n):
        self.uf = UnionFind(n)
    
    def add_friendship(self, a, b):
        self.uf.union(a, b)
    
    def are_friends(self, a, b):
        return self.uf.connected(a, b)
    
    def get_connected_components(self):
        components = {}
        for i in range(self.uf.parent):
            root = self.uf.find(i)
            if root not in components:
                components[root] = []
            components[root].append(i)
        return list(components.values())

11.2 图的连通分量统计

def count_connected_components(graph, n):
    uf = UnionFind(n)
    
    for u, v in graph.edges:
        uf.union(u, v)
    
    # 统计不同的根节点数量
    roots = set()
    for i in range(n):
        roots.add(uf.find(i))
    
    return len(roots)

12. 总结

并查集是一种非常实用的数据结构，特别适合处理动态连通性问题。通过路径压缩和按秩合并等优化技术，它能够在几乎常数时间内完成查找和合并操作。在实际应用中，并查集被广泛应用于图算法、网络分析、等价类划分等领域。

选择并查集时需要考虑：

• 问题是否涉及动态连通性
• 是否需要高效的查找和合并操作
• 是否可以接受不支持分割操作的限制