并查集

并查集，是一种高级数据结构，常用于数据分组问题。本文简单介绍一下并查集相关概念以及实现方法，并附带一些leetcode练习题。

并查集基本知识

并查集，和堆十分类似，两者本质上描述的都是一种树状数据结构。不过堆是一棵树，而并查集表示的是一个森林。森林中的每棵树（也叫连通分量）可以看作一个分组，因此常被用于数据分组问题。

• 底层数据结构：和堆一样，不需要实际定义树结构，依赖数组就可以实现并查集

  • parent数组：记录每个元素的parent下标。
  • index数组：记录每个元素在数组中的下标。

  比如，下图展示了parent数组和index数组构成的一个森林，由2棵树构成：

  

• 操作：并查集主要支持2种操作，合并和查询

  • 查询：find(int x)，查询x节点所在树的根节点，下面给出基本版本的查询操作

    public int find(int x){
        //一直往上，直到根节点
        while(x != parent[x])
            x = parent[x];
       	return x;
    }

  • 合并：union(int x, int y)，把x和y所在的两棵树合并到一起，下面给出基本版本的合并操作

    public void union(int x, int y){
        int rootX = find(x);
        int rootY=find(y);
        if(rootX == rootY) return;
        //把x所在树的根节点的父亲，设置成y所在树的根节点
        parent[rootX] = rootY;
    }

    

并查集进阶

从前面的介绍中，我们知道find()的效率和树的高度有关，树越高，查询效率越低。 如果 union 操作直接将两棵树合并，那么多次 union 之后，树的高度可能会很高，那该如何对其进行优化呢？主要有两种优化方式，那就是路径压缩和按秩合并，路径压缩是在 find 方法里进行，而按秩合并则是在 union 方法中进行。

路径压缩

路径压缩又有两种方式：隔代压缩和彻底压缩

• 「隔代压缩」性能比较高，虽然压缩不完全，不过多次执行「隔代压缩」也能达到比较好的效果，只需要在原 find 方法中加上一句parent[x] = parent[parent[x]];这句代码的意思是把路径上的每个节点的父节点指向其祖父节点。
• 「彻底压缩」需要借助系统栈，使用递归的写法 。或者使用迭代写法，先找到当前结点的根结点，然后把沿途上所有的节点都指向根节点，需要遍历两次。彻底压缩需要消耗更多的性能，但是压缩的更彻底，可以提高查询效率。

按秩合并

所谓按秩，可以理解成树的高度，合并的时候，把矮树合并到高树上面。那具体要怎么实现呢？

我们用一个rank数组，表示每个元素作为根节点时，树的高度。我们将rank中所有元素初始化为1，合并时，比较两个根节点的rank值，把rank较小的往较大者上合并。按秩合并的代码实现如下：

 /**按秩合并*/
public void union(int x, int y) {
    int rootX = find(x), rootY = find(y);
    if (rootX == rootY) return;
    //把高度小的合并到高度大的树上
    if (ranks[rootX] > ranks[rootY]) {
        parent[rootY] = rootX;
    } else if (ranks[rootX] < ranks[rootY]) {
        parent[rootX] = rootY;
    } else {//高度一样，随便怎么合并都行，高度+1
        parent[rootY] = rootX;
        ranks[rootX]++;
    }
    count--;
}

练习题

基础题

1. 547. 省份数量：给定若干个城市，相连的城市属于同一个省份，问一共有多少个省份。其实就是求连通分量的个数。
2. 990. 等式方程的可满足性：给定一个由表示变量之间关系（==或者!=）的字符串方程组成的数组，判断这些方程能否同时满足。其实就是判断不等式左右2个节点是否在同一个连通分量。
3. 684. 冗余连接：环路检测，添加边的时候，如果两个节点已经存在于同一个连通分量，这条边就是冗余的。
4. 1319. 连通网络的操作次数：同上，环路检测，添加边的时候，判断节点是否存在于同一个连通分量。
5. 200. 岛屿数量：这题用DFS比较简单，并查集解法不容易发现。把边界相连的O放到同一个连通分量。

进阶题

这些题并不是“并查集”的实现上有多难，难在于“比较难看出怎么将原始问题转换成直观的并查集问题”。

1. 685. 冗余连接 II ：和冗余连接1类似，不过换成了有向图，变得更加复杂，需要分情况讨论。
2. 778. 水位上升的泳池中游泳：并查集解法比较难想，对路径最大值进行二分衍生出并查集解法，问题转化成“遍历0~max，对于0 < threshold <= max，判断左上角和右下角是否在一个连通图中”

参考资料

1. https://segmentfault.com/a/1190000022952886

打赏