并查集（Union Find）算法原理

labuladong原创约 2897 字

前置知识

阅读本文前，你需要先学习：

一句话总结

并查集（Union Find）结构是二叉树结构的衍生，用于高效解决无向图的连通性问题，可以在 $O(1)$ 时间内合并两个连通分量，在 $O(1)$ 时间内查询两个节点是否连通，在 $O(1)$ 时间内查询连通分量的数量。

并查集算法有几种优化方法，可视化面板都做了支持。下面展示一个未经优化的并查集实现，最终多叉树几乎退化成单链表，导致算法效率降低。对于这个问题的优化思路和可视化展示，在下文中会详细介绍。

本文将介绍什么是图的动态连通性问题，以及为什么并查集（Union Find）算法能够高效解决动态连通性问题。

本文会结合可视化面板直观展示 Union Find 算法的核心原理，以及几种优化思路的效果。

考虑到这是基础章节，本文不涉及算法代码的实现细节。具体的代码实现和算法题的运用放在后面的 Union Find 算法实现及应用和并查集经典习题章节中，建议初学者按照目录顺序循序渐进地学习。

动态连通性及术语

图论算法中专业术语比较多，我就用一个简单的例子来介绍几个专业术语。

比如下面这个例子，其中有 10 个节点，分别用 0~9 标记，虽然其中没有边，但它依然是一个图结构：

我们可以说这个图结构中，有 10 个「连通分量」，每个节点自身都是一个连通分量，因为它们自成一派，没有和其他节点相连。

现在将其中的一些节点进行「连接操作」：

此时，图结构中的节点 0,1,2 之间就有了连接关系，它们三个节点共同构成了一个连通分量，我们可以说这三个节点是「连通」的。

同时，这个图结构中的连通分量的数量从 10 减少到了 8，因为连接操作将多个连通分量合并成了一个。

连通关系的性质

1、自反性：节点 p 和 p 是连通的。

2、对称性：如果节点 p 和 q 连通，那么 q 和 p 也连通。

3、传递性：如果节点 p 和 q 连通，q 和 r 连通，那么 p 和 r 也连通。

判断这种「等价关系」非常实用，比如说编译器判断同一个内存对象的不同变量引用，比如社交网络中的朋友圈计算等等。

那么动态连通性问题就是说，给你输入一个图结构，然后进行若干次「连接操作」，同时可能会查询任意两个节点是否「连通」，或者查询当前图中有多少个「连通分量」。

我们的目标是设计一种数据结构，在尽可能小的时间复杂度下完成连接操作和查询操作。

并查集（Union Find）结构提供如下 API：