什么是并查集？并查集的典型应用场景

· 日常编程 · 95113

并查集通过维护一个森林结构来高效处理集合的合并与查询问题，其核心操作为find和union。find操作用于确定元素所属集合的根节点，并通过路径压缩优化，将查找路径上的所有节点直接连接到根，从而提升后续查询效率；union操作用于合并两个不同集合，通常结合按秩或按大小合并的策略，即将较小树的根连接到较大树的根上，以控制树的高度，避免退化为链表。这两种优化共同作用，使并查集的平均时间复杂度接近常数级别，远优于未优化时的O(N)。在实际应用中，并查集广泛用于判断图的连通分量、实现Kruskal算法构建最小生成树、解决朋友圈问题、计算岛屿数量以及处理动态连通性查询等场景。实现时需注意正确初始化parent数组，确保每个元素初始时指向自身，同时保证路径压缩和按秩合并逻辑的正确性，防止数组越界、循环引用等问题，才能充分发挥其性能优势。因此，并查集是一种在算法设计中极为实用且高效的工具。

并查集，一种在计算机科学中，尤其是在算法领域里，算是个挺巧妙也挺实用的数据结构，专门用来解决那些关于集合合并与元素归属的问题。简单讲，它能帮你快速判断两个元素是不是在一个集合里，以及把两个不相交的集合合二为一。它的核心思想，其实就是用一个树形结构来表示集合，树的根节点就是这个集合的代表元素。

并查集的核心思想，在于它维护了一个“森林”，每棵树都代表一个独立的集合。要理解它怎么解决问题，得从它的两个基本操作说起：

find

（查找）和

union

（合并）。

find

操作的目的，是找到一个元素所属集合的代表元素，也就是这棵树的根。我们通常会用一个数组 

parent

来存储每个元素的父节点，如果 

parent[i] == i

，那么 

i

就是一个集合的根。查找的时候，如果当前节点不是根，就一直向上找它的父节点，直到找到根为止。这里有个非常关键的优化，叫做“路径压缩”。你想想，每次查找都从叶子节点走到根，如果树很高，效率就低了。路径压缩就是，在查找过程中，把经过的所有节点直接连接到根节点上。这样，下次再查这些节点，就能一步到位。

union

操作，顾名思义，就是将两个集合合并。假设我们要合并元素 

a

和 

b

所在的集合，我们先分别找到 

a

和 

b

的根节点 

rootA

和 

rootB

。如果 

rootA

和 

rootB

相同，说明它们已经在同一个集合里了，不用做任何事。如果不同，我们就把其中一个根节点设为另一个根节点的子节点。听起来很简单，但这里也有个优化，叫做“按秩合并”（union by rank）或者“按大小合并”（union by size）。简单来说，就是把小树的根连接到大树的根下面，这样可以有效控制树的高度，避免出现“扁平化”或者“退化”成链表的情况，从而保证查找效率。如果不做这些优化，并查集的性能会大打折扣，甚至可能退化到O(N)的复杂度。但有了路径压缩和按秩/大小合并，它的平均时间复杂度可以达到近乎常数级别，也就是阿克曼函数的反函数，非常高效。

并查集是如何工作的？核心操作与优化技巧解析

并查集的工作机制，说到底就是对 

parent

数组的巧妙操作。每个元素 

i

，

parent[i]

存储的是它的直接父节点。如果 

parent[i] == i

，那么 

i

就是它所在集合的“老大”。

find(i)

的实现，通常是这样的：

int find(int i) {
    if (parent[i] == i) { // 如果i是根节点
        return i;
    }
    // 路径压缩：直接把i的父节点指向根节点
    return parent[i] = find(parent[i]); 
}

这个递归调用，在回溯的时候，会把路径上的所有节点都直接挂到最终的根节点下面。比如，你从节点5开始找根，路径是 5 -> 3 -> 1 (根)。路径压缩后，5的父节点会直接变成1，3的父节点也会直接变成1。下次再查5或3，就快多了。

union(i, j)

的实现，通常是这样的（以按秩合并为例）：

void unionSets(int i, int j) {
    int rootI = find(i);
    int rootJ = find(j);

    if (rootI != rootJ) { // 如果不在同一个集合
        // 比较秩（rank），把秩小的树连接到秩大的树下面
        // 秩可以理解为树的高度或大小的近似
        if (rank[rootI] < rank[rootJ]) {
            parent[rootI] = rootJ;
        } else if (rank[rootJ] < rank[rootI]) {
            parent[rootJ] = rootI;
        } else { // 如果秩相同，随便一个作为另一个的父，并增加新根的秩
            parent[rootJ] = rootI;
            rank[rootI]++; 
        }
    }
}

这里的 

rank

数组，初始化时所有元素的 

rank

都为0。每次合并时，只有当两个根的秩相等时，合并后的新根的秩才会增加1。这确保了树的高度尽可能地保持平衡，避免了深度过大的问题。没有这些优化，并查集在极端情况下可能会退化成链表，导致每次操作都是 O(N) 的时间复杂度，这在处理大量数据时是不可接受的。

并查集在哪些实际问题中大显身手？典型应用场景一览

并查集在很多算法问题中都有着不可替代的作用，尤其是在处理“连通性”和“分组”这类问题时，它简直是神器。

  1. 判断图的连通分量： 这是最经典的用法。比如，给你一堆城市和它们之间的道路，想知道哪些城市是互相可达的？或者，有多少个独立的城市群？每次遇到一条边 

    (u, v)

    ，就对 

    u

    和 

    v

    所在的集合进行 

    union

    操作。最后，统计有多少个不同的根节点，就是有多少个连通分量。Kruskal 算法构建最小生成树时，就大量依赖并查集来判断加入的边是否会形成环，以及合并连通分量。

  2. 朋友圈问题： 假设社交网络里，如果A认识B，B认识C，那么A、B、C就在一个朋友圈里。给你一系列“认识”关系，让你找出总共有多少个朋友圈。这本质上就是判断连通分量的问题。把每个人看作一个节点，认识关系看作边，用并查集来合并认识的人，最终统计根节点的数量。

  3. 岛屿数量问题： 在一个二维网格中，'1' 代表陆地，'0' 代表水域。相邻的陆地单元格形成一个岛屿。问有多少个岛屿？你可以遍历网格，遇到 '1' 就把它加入并查集，并检查它的上下左右四个方向，如果也是 '1'，就将它们合并。最后统计并查集中有多少个独立的集合。

  4. 动态连通性查询： 在某些需要频繁添加边并查询两点是否连通的场景中，并查集表现出色。比如，网络拓扑变化，或者游戏地图中区域的连通性变化。

  5. 一些复杂的图论问题： 除了Kruskal，还有一些涉及集合划分、等价关系的问题，都可以用并查集来建模和解决。比如，判断给定关系是否能形成一个有效的等价关系组。

这些场景，共同点都是需要高效地进行集合的合并和元素的归属查询。并查集以其优秀的性能，成为了解决这类问题的首选。

实现并查集时常见的陷阱与性能考量

虽然并查集的概念和实现相对直观，但在实际编码过程中，还是有一些细节需要注意，否则可能导致性能问题甚至逻辑错误。

  1. 初始化： 这是最基础但又容易被忽略的一步。在开始任何操作之前，每个元素都应该被视为一个独立的集合，即 

    parent[i] = i

    。如果漏掉这一步，或者初始化错误，后续的 

    find

    和 

    union

    操作都会出问题。

  2. 路径压缩的正确实现： 路径压缩是并查集高效的关键。错误的路径压缩实现，比如只压缩了当前节点而没有递归地压缩路径上的所有节点，或者在递归过程中没有正确更新父节点，都会导致性能下降。上面给出的 

    return parent[i] = find(parent[i]);

    是最简洁且正确的写法。

  3. 按秩/大小合并的必要性： 尽管路径压缩已经非常强大，但如果没有按秩或按大小合并，并查集在最坏情况下仍然可能退化成一条链，导致 

    find

    操作的时间复杂度回到 O(N)。例如，每次都把一个大集合连接到一个小集合下面，这会导致树的高度失控。因此，这两个优化通常是配套使用的，它们共同保证了并查集的近乎常数时间复杂度。

  4. 数组越界问题： 如果你的元素编号是从0到N-1，那么 

    parent

    和 

    rank

    数组的大小至少应该是N。如果元素编号不连续或者范围很大，需要考虑映射或者使用哈希表来存储。

  5. 循环引用或死循环： 在实现 

    find

    函数时，如果逻辑有误，可能会导致 

    parent[i]

    最终指向自己，但没有正确地处理递归终止条件，或者形成了循环引用，从而陷入死循环。不过，只要按照标准模板实现，并注意 

    parent[i] == i

    作为递归基，通常不会出现这个问题。

  6. 数据类型选择： 对于 

    parent

    和 

    rank

    数组的索引，通常使用 

    int

    即可。但如果元素数量非常庞大（例如超过 

    int

    的最大范围），可能需要考虑 

    long long

    ，但这在大多数竞赛和实际问题中并不常见。

总的来说，并查集是一个非常实用的数据结构，它以简洁的逻辑和强大的性能，解决了大量关于集合操作的问题。理解其核心原理和优化技巧，并在实现时注意这些细节，就能充分发挥它的威力。

以上就是什么是并查集？并查集的典型应用场景的详细内容，更多请关注骃骐网【www.myinqi.com】。

相关推荐：

Python Web框架怎么选_Django与Flask在不同场景下的适用分析

Django适合中型业务系统，因其开箱即用的admin、ORM、auth等组件；Flask适合轻量、嵌入式或高度定制场景，如微服务或IoT网关。 什么时候该用 Django 而不是 Flask 如果你要快速上线一个带用户管理、后台编辑、数据库迁移、API 和权限控制的中型业务系统，Django 是更省力的选择。它自带 admin、ORM、auth、forms、migrations，这些不是“可选插...

Python 中整数除法的多种实现方式及其适用场景

本文详解 Python 中 int(x / y) 与 x // y 在语义、精度、性能和边界行为上的本质差异，指出二者结果并不等价，并系统对比其适用场景，同时介绍位运算等高效替代方案。 本文详解 python 中 `int(x / y)` 与 `x // y` 在语义、精度、性能和边界行为上的本质差异，指出二者结果并不等价，并系统对比其适用场景，同时介绍位运算等高效替代方案。 在 Python 中...

深入理解JavaScript Promise的执行顺序：多链并发场景解析

本文旨在深入探讨JavaScript中多个独立Promise链的执行顺序。我们将阐明Promise内部的then回调如何确保顺序执行，同时揭示为何不同Promise链之间的执行顺序可能不确定。通过解析JavaScript的事件循环和微任务队列机制，我们将解释这种非确定性行为的根本原因，并提供在并发场景下管理Promise执行顺序的专业指导。JavaScript事件循环与Promise微任务 在深入...

深入理解JavaScript Promise执行顺序：多链并发场景解析

本文深入探讨JavaScript中Promise的执行顺序，重点解析在存在多个独立Promise链时，链内顺序的确定性与链间顺序的不确定性。文章将通过示例代码阐明微任务队列的工作机制，揭示为何期望输出与实际输出可能存在差异，并提供最佳实践建议，以有效管理异步操作的执行流。在javascript异步编程中，promise是管理复杂回调和链式操作的核心工具。然而，当涉及多个独立的promise链并发执...

C++匿名联合体应用 特殊内存访问场景

匿名联合体允许同一内存被不同类型的成员共享，直接通过外层结构体访问，适用于类型双关、硬件寄存器映射和内存优化；但易引发未定义行为，尤其在跨类型读写时，需谨慎使用volatile、避免严格别名违规，并优先采用memcpy或std::bit_cast等安全替代方案。 C++的匿名联合体，在我看来，是一把双刃剑，用得好能让你在某些特定场景下，比如底层硬件交互或内存优化时，获得极高的灵活性和效率。它允许你...

SOAP的优缺点有哪些？适用于什么场景？

SOAP的优点在于标准化高、安全性强、支持事务和跨平台，适用于企业级系统集成；缺点是复杂、性能开销大、学习成本高。其WSDL文件定义服务接口，实现自动化开发与契约化通信；通过WS-Security等扩展实现消息级安全，保障完整性、机密性和不可否认性。选择SOAP还是REST应根据业务需求权衡。 SOAP（Simple Object Access Protocol）的优缺点在于其严谨的标准化和安全性...

Vue中computed和watch的使用场景有什么区别？

computed 适合基于已有数据同步计算新值，具有缓存机制，适用于格式化文本、过滤数组、判断状态等场景；例如通过 fullname 计算姓氏和名字的拼接。watch 则适合监听数据变化后执行异步或复杂操作，如发送 api 请求、深度监听对象变化，例如监听 searchquery 发起搜索或使用 deep: true 监听 userinfo 的深层变化。选择时应明确用途，生成新数据优先用 comp...

Python中装饰器基础入门教程 Python中装饰器使用场景

Python装饰器通过封装函数增强功能，实现日志记录、权限校验、性能监控等横切关注点的分离。 Python装饰器本质上就是一个函数，它能接收一个函数作为参数，并返回一个新的函数。这个新函数通常在不修改原有函数代码的基础上，为其添加额外的功能或行为。它让我们的代码更模块化、可复用，并且更“优雅”地实现功能的增强或修改。它在很多场景下都能提升代码的可读性和可维护性，比如日志记录、性能监控、权限校验、缓...

C++匿名联合体使用 特殊内存访问场景实现

匿名联合体是一种内存复用机制，允许在同一内存位置存储不同类型的数据，其成员可直接被外部访问而无需额外层级，常用于协议解析、硬件寄存器操作等对内存布局敏感的场景，提升访问效率与代码简洁性。 C++的匿名联合体，在我看来，它就是一种非常巧妙的内存复用机制，尤其在处理那些需要对同一块内存有多种解释，或者内存资源极其紧张的场景下，它能发挥出意想不到的作用。 解决方案 匿名联合体，顾名思义，就是没有名字的联...

C++原子操作代价 无锁编程适用场景

原子操作和无锁编程适用于低冲突、高并发场景，如单生产者单消费者队列、引用计数、状态标志更新和高性能计数器；其代价包括内存序开销、缓存行伪共享和CAS重试，尤其在高竞争或复杂操作中性能反不如锁；合理选择memory_order并避免伪共享可提升效率，但多数情况下应优先使用互斥锁以降低复杂度。 原子操作和无锁编程在C++中常用于提升多线程程序的性能，但它们并非“银弹”。理解其代价和适用场景，才能合理使...