「并查集」专题 1：并查集简介

专题 11：并查集

发布日期: 2017-10-16

重点提示

「并查集」是一种建立在「数组」上的树形结构，并且这棵树的特点是孩子结点指向父亲结点；

「并查集」主要用于解决「动态连通性」问题，重点关注的是连接问题，并不关注路径问题；

「并查集」是树，所以优化的策略依然是和树的高度较劲，优化思路有「按秩合并」与「路径压缩」。

「并查集」主要知识点如下：

「并查集」这部分知识点讲得最清楚的是《算法》（第 4 版），本篇「并查集」的介绍是我看这本书第 1.5 节的学习笔记。

高级数据结构：并查集-1

高级数据结构：并查集-2

高级数据结构：并查集-3

什么是「并查集」

我们知道，「堆」是一种建立在数组上的「树结构」，在这一章，我们向大家介绍的数据结构同样也是建立在数组上的树结构，这个数据结构叫做「并查集」（Union-Find），「并查集」也叫做「不相交集合」（Disjion-Sets）。

「并查集」的设计思想很简单，易于理解，且代码编写容易，难点在于如何应用并查集的思想解决问题。能够使用并查集解决的问题一般来说都比较生活化，还比较有趣。

在这里需要和大家说明的是：并查集的问题在面试中的占比较少，并且由于并查集问题通常不以并查集为背景，故「力扣」上「并查集」的问题一般被标记为「中等」和「困难」。

建议：完成「力扣」上的一些经典和常见问题即可。在时间比较充裕的情况下，才考虑完成一些你所感兴趣的，较难的问题。

什么是「并」和「查」

并查集主要提供了以下两个操作，并别就是「并查集」这个名字中的前两个字：

1、我们先说「并」：并是把两个集合合并成一个集合，表示这两个集合之间产生连接；

2、再说「查」：查询元素属于哪个集合，但我们更经常用于查询两个元素是不是连接在一起

这两个操作其实在我们的生活中都能看到影子。我们和人见面，最先问的几句话可能就是「你是哪里人」、「你在哪上班」、「你是做什么工作的」。根据询问到的结果，判断我们是不是适合做同事、做朋友。

因此，如果我们在一些场景下，只需要查询两个事物之间是否有联系，「并查集」就是一个不错的选择。例如：查询两个人是不是好友关系（「力扣」第 547 题：「朋友圈」），查询从一个地方到另一个地方是否能走通（「力扣」第 130 题：被包围的区域）。

「并查集」与「路径问题」

并查集主要用于解决连通问题，即抽象概念中结点和结点是否连接。

路径问题，不仅仅要考虑连通问题，我们还要往往还需要求出最短路径，这不是并查集做的事情。因此并查集问题能做的事情比路径问题少，它更专注于

判断连接状态（查）；
改变连接状态（并）。

具体说来，并查集的代码需要实现以下的 3 个功能：

1、 find(p)：查找元素 p 所对应的集合，

说明：这个函数有些时候仅作为私有函数被下面两个函数调用。

2、 union(p, q)：合并元素 p 和元素 q 所在的集合。

3、 isConnected(p, q)：查询元素 p 和元素 q 是不是在同一个集合中。

因此，我们要实现的并查集其实就是要实现下面的这个接口：

Java 代码：

public interface IUnionFind {

    // 并查集的版本名称，由开发者指定
    String versionName();

    // p (0 到 N-1)所在的分量的标识符
    int find(int p);

    // 如果 p 和 q 存在于同一分量中则返回 true
    boolean isConnected(int p, int q);

    // 在 p 与 q 之间添加一条连接
    void union(int p, int q);

}