并查集：从原理到实战的全面解析
2026-05-21 07:54:54
发布于：广东
并查集：从原理到实战的全面解析
开篇引言
各位老师、同学、朋友们，大家好！今天我们要深入学习一个在数据结构与算法领域中，结构极简、效率极高、应用极广的核心工具 ——并查集（Union-Find，全称 Disjoint Set Union，简称 DSU）。在算法学习的旅程中，我们会遇到无数关于 “连通性”“分组”“合并” 的问题：比如判断两个人是否是亲戚、多个岛屿是否连通、网络中的节点是否相连、最小生成树如何构建…… 这些看似不同的问题，本质上都指向同一个核心需求：动态维护不相交集合，快速查询元素所属集合，快速合并两个集合。而并查集，就是专门为解决这类问题而生的最优解。
很多人初次接触并查集，会觉得它代码简短、原理简单，容易轻视它的价值；但真正深入应用后会发现，它是解决连通性问题的 “万能钥匙”，是算法竞赛、工程开发、数据处理中不可或缺的基础工具。今天，我们就从核心定义、底层原理、基础实现、关键优化、时间复杂度、经典应用、实战案例、拓展变形八个维度，全面、系统、深入地讲解并查集，让大家不仅能听懂、会写代码，更能理解其背后的思想，灵活运用到各类问题中。
一、并查集的核心定义与本质
1.1 什么是并查集？
并查集，顾名思义，核心就是两个操作：“并”（合并）和“查”（查找）。它是一种树形数据结构，用于处理动态连通性问题—— 即我们需要频繁地将两个集合合并，同时频繁地查询两个元素是否属于同一个集合。
这里的 “集合”，可以理解为一个连通块、一个分组、一个家族：比如朋友圈是一个集合，亲戚圈是一个集合，连通的岛屿是一个集合，网络中的连通节点是一个集合。并查集的作用，就是高效管理这些互不相交的集合，支持合并两个集合、查询元素所在集合的代表、判断两个元素是否同属一个集合三大核心功能。
1.2 并查集的核心特性
并查集之所以成为最优解，源于它的三大核心特性：
动态性：支持在线处理，即可以随时合并集合、随时查询，不需要预先知道所有操作；
高效性：经过优化后，单次操作的时间复杂度几乎是常数级，远优于其他数据结构；
简洁性：代码实现极简，逻辑清晰，不需要复杂的存储结构，仅用一个数组即可完成。
1.3 适用场景：哪些问题用并查集？
只要问题满足 “动态连通性”，就可以用并查集解决，典型场景包括：
社交关系：判断两人是否是朋友 / 亲戚，合并两个社交圈；
图论问题：判断无向图的连通性，检测图中是否存在环，计算连通块数量；
最小生成树：Kruskal 算法的核心辅助工具；
网格问题：岛屿数量、连通区域合并；
工程应用：网络连通性检测、文件分组、任务合并。
简单来说：只要涉及 “分组、合并、查是否同组”，优先想并查集。
二、并查集的底层原理：从生活到逻辑
为了让大家彻底理解并查集的原理，我们先从生活案例入手，再转化为数据结构逻辑。
2.1 生活类比：家族族谱
最经典的并查集类比，就是家族族谱：
每一个人，都是一个独立的元素；
每一个家族，都是一个集合；
家族的族长，就是集合的根节点（代表元素）；
一个人的父亲，就是他在树形结构中的父节点；
判断两个人是否是同一家族：看他们的族长是不是同一个人；
合并两个家族：让一个家族的族长，认另一个家族的族长为父亲。
这个类比完美对应并查集的所有操作：
初始化：每个人刚出生，自己是自己的族长（父节点是自己）；
查找（查）：找一个人的最终族长（找根节点）；
合并（并）：让两个家族的族长建立父子关系，合并为一个家族。
2.2 数据结构抽象：树形结构
从数据结构角度，并查集是一棵多叉树（通常简化为链式结构），每一个节点存储父节点的编号：
用一个数组parent[]表示，parent[i]表示元素i的父节点；
根节点的特征：parent[root] = root（自己是自己的父节点）；
非根节点：parent[i]指向它的直接父节点，最终追溯到根节点。
举个例子：初始时，元素 1、2、3、4、5 各自独立，parent[1]=1，parent[2]=2，parent[3]=3，parent[4]=4，parent[5]=5，每一个元素都是一棵独立的树。
当我们合并 1 和 2：让 1 的父节点指向 2，此时parent[1]=2，2 是根节点，1 和 2 属于同一个集合。
再合并 2 和 3：让 2 的父节点指向 3，此时parent[2]=3，3 是根节点，1、2、3 属于同一个集合。
此时查询 1 和 3 是否同组：追溯 1 的父节点→2，再追溯 2 的父节点→3（根节点）；3 的父节点是自己，两者根节点相同，属于同一集合。
这就是并查集最基础的逻辑：用树形结构表示集合，用根节点代表集合，通过追溯父节点完成查询，通过修改根节点的父节点完成合并。
三、并查集的基础实现：代码与步骤
理解原理后，我们来看并查集的基础实现，分为初始化、查找、合并三个核心步骤，所有编程语言的实现逻辑完全一致，这里以最常用的 C++ 和 Python 为例，方便大家理解。
3.1 基础数据结构：父节点数组
并查集只需要一个一维数组parent[]，长度等于元素的最大数量。数组的下标代表元素本身，数组的值代表该元素的父节点。
3.2 步骤一：初始化（Init）
初始化的逻辑很简单：每一个元素的父节点都是自己，因为初始时每个元素都是独立的集合，自己是自己的根节点。
const int MAXN = 10005; // 元素最大数量
int parent[MAXN]; // 父节点数组
// 初始化n个元素
void init(int n) {
for (int i = 1; i <= n; i++) {
parent[i] = i; // 自己是自己的父节点
}
}
3.3 步骤二：查找操作（Find）：找根节点
查找操作的核心目的：找到一个元素所在集合的根节点。
基础查找的逻辑：递归或循环，不断追溯父节点，直到找到parent[x] == x的节点，即为根节点。
// 查找元素x的根节点
int find(int x) {
// 如果父节点不是自己，继续查找父节点的根节点
if (parent[x] != x) {
return find(parent[x]);
}
// 父节点是自己，返回根节点
return x;
}
int find(int x) {
// 循环追溯父节点
while (parent[x] != x) {
x = parent[x];
}
return x;
}
惊天先这样
这里空空如也
有帮助，赞一个