52 | 理论讲解：并查集-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

### 52 | 理论讲解：并查集

在算法与数据结构的广阔天地中，并查集（Union-Find）是一种高效处理一些不交集合（Disjoint Sets）合并及查询问题的数据结构。它以其简洁的实现和高效的性能，在诸如网络连通性、动态连通性判断、等价类划分等场景中发挥着重要作用。本章将深入剖析并查集的基本原理、实现方式及其优化策略，帮助读者在算法面试中轻松应对相关难题。

#### 一、并查集的基本概念

并查集，顾名思义，是一种支持两种操作的数据结构：
1. **合并（Union）**：将两个不相交的集合合并为一个集合。
2. **查找（Find）**：查询某个元素所在的集合的代表元素（或称根节点）。

并查集的核心思想在于通过维护每个元素的“父节点”信息来快速判断元素间的连通性。在初始状态下，每个元素各自构成一个集合，即每个元素的父节点指向自己。随着合并操作的进行，集合的结构逐渐变化，但每个集合内部始终保持一个树状结构，其中根节点（父节点指向自己的节点）代表整个集合。

#### 二、并查集的基本实现

##### 2.1 初始化

初始化时，每个元素都作为一个独立的集合，即每个元素的父节点都指向自己。这可以通过一个数组`parent`来实现，其中`parent[i]`表示元素`i`的父节点。

```python
def initialize(n):
    parent = [i for i in range(n)]
    return parent
```

##### 2.2 查找（Find）

查找操作的目标是找到元素所在集合的根节点。由于集合内部以树状结构组织，因此查找过程可以沿着父节点链向上遍历，直到找到根节点（即父节点指向自己的节点）。为了优化查找效率，通常会在查找过程中进行路径压缩，即将查找路径上的每个节点的父节点直接指向根节点，从而减少后续查找的时间复杂度。

```python
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # 路径压缩
    return parent[x]
```

##### 2.3 合并（Union）

合并操作将两个集合合并为一个集合。首先，通过查找操作找到两个集合的根节点，然后将其中一个根节点的父节点设置为另一个根节点，从而完成合并。在实际应用中，为了保持树的平衡（尽管并查集并不严格要求树平衡，但平衡性有助于减少查找时间），通常会选择将较小的树合并到较大的树上，或者采用按秩合并的策略。

```python
def union(parent, rank, x, y):
    rootX = find(parent, x)
    rootY = find(parent, y)
    if rootX != rootY:
        # 按秩合并，这里简化处理，直接合并
        parent[rootX] = rootY
        # 如果需要，可以更新rank数组以保持树的平衡
```

#### 三、并查集的优化策略

##### 3.1 路径压缩

路径压缩是并查集中最常用的优化手段之一。在查找过程中，将查找路径上的每个节点的父节点直接指向根节点，可以显著减少后续查找操作的时间复杂度。路径压缩后，任意两个节点的查找时间复杂度均接近常数时间。

##### 3.2 按秩合并

按秩合并是另一种优化策略，旨在保持合并后树的平衡性。在并查集中，每个节点除了记录父节点信息外，还可以额外记录一个“秩”信息，表示以该节点为根的子树的高度（或节点数）。合并时，选择秩较小的树作为子树合并到秩较大的树上，可以保持合并后树的平衡性，减少树的高度，进而优化查找效率。

#### 四、并查集的应用场景

##### 4.1 网络连通性

并查集最直观的应用之一是解决网络连通性问题。给定一个无向图，通过并查集可以高效地判断图中任意两个节点是否连通，以及进行边的添加操作后连通性的变化。

##### 4.2 动态连通性判断

在动态图（即边可以动态添加或删除的图）中，并查集同样能够高效地处理连通性查询和更新。虽然标准的并查集不支持边的删除操作，但可以通过记录历史状态或使用更高级的数据结构（如可持久化并查集）来模拟删除操作。

##### 4.3 等价类划分

在某些问题中，需要将具有某种等价关系的元素划分为不同的等价类。并查集可以高效地实现这一过程，通过合并操作将具有等价关系的元素归入同一集合，并通过查找操作判断任意两个元素是否属于同一等价类。

#### 五、总结

并查集作为一种高效处理不交集合合并及查询问题的数据结构，在算法与数据结构的领域中占据着重要地位。通过掌握并查集的基本原理、实现方式及其优化策略，读者可以更加灵活地应对各种与连通性、等价类划分相关的问题。在算法面试中，熟练掌握并查集的应用，不仅能够提升解题效率，还能展现出扎实的算法功底和灵活的思维能力。希望本章内容能为读者在算法面试中通关并查集相关题目提供有力支持。

该分类下的相关小册推荐：

编程之道-算法面试(下)

业务开发实用算法精讲

数据结构与算法之美

编程之道-算法面试(上)

数据结构与算法(上)

数据结构与算法(下)

数据结构与算法(中)