数据结构面试题 | 并查集 & 联合 - 查找算法

2020-09-24 本文已影响0人彭旭锐

前言

并查集是一种非常适用于处理 动态连通 问题的数据结构，在面试中比较冷门，建议应试者合理安排学习时间；
在这篇文章里，我将梳理并查集的基本知识 & 常考题型。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。

系列文章

延伸文章

算法面试题 | 高楼丢鸡蛋（源自谷歌面试题）

`并查集`	提示 & 题解
990. 等式方程的可满足性 Satisfiability of Equality Equations	【题解】
547. 朋友圈 Friend Circles	【题解】
684. 冗余连接 Redundant Connection	【题解】
685. 冗余连接 II Redundant Connection II
1319. 连通网络的操作次数 Number of Operations to Make Network Connected	【题解】
399.除法求值 Evaluate Division
952. 按公因数计算最大组件大小 Largest Component Size by Common Factor
130. 被围绕的区域 Surrounded Regions
128. 最长连续序列 Longest Consecutive Sequence
721. 账户合并 Accounts Merge
765. 情侣牵手 Couples Holding Hands

1. 定义

并查集还有多个相同的名字：不相交集合（Disjoint Sets）、合并-查找集合（Merge-find Set）、联合-查询数据结构（Union-find Data Structure）、联合-查询算法（Union-find algorithm），从这么多的相似概念中，我们可以体会到并查集解决的问题，即：处理不相交集合的合并和查询。

具体来说，用于一对元素是否相连。因为元素之间的关系并不是一开始就可以确定的，所以需要一边查询一边连接（合并），这种问题叫做动态连通性问题。举个例子，990. Satisfiability of Equality Equations 等式方程的可满足性

引用自 LeetCode

2. 并查集的实现

并查集在底层实现可以是数组，也可以是散列表，不管使用什么底层实现，关键在于能表示一个对应关系，即：key 或下标表示了节点本身，而 value 表示顶点的父亲节点，初始化时指向自己。

一般来说，当节点总个数固定不变 / 已知时，使用数组，否则使用散列表。例如在 990. Satisfiability of Equality Equations 等式方程的可满足性这道题中，节点是已知的 26 个字母，此时使用数组即可；在 684. Redundant Connection 冗余连接这道题中，节点个数是未知的，此时使用散列表更合适。

基于数组
class UnionFind(n: Int) {
    1. 初始时，节点指向自己
    val parent = IntArray(n) { it } 
    ...
}
-------------------------------------------------------
基于散列表
class UnionFind() {
    val parent = HashMap<Int, Int>()
    
    fun find(x: Int): Int {
        1. 首次查询时，添加到散列表，并指向自己
        if (null == parent[x]) {
            parent[x] = x
        }
        var key = x
        while (parent[key] != key) {
            parent[key] = parent[parent[key]]!!
            key = parent[key]!!
        }
        return key
    }
}

提示
这里为不熟悉 Kotlin 的同学解释一下，IntArray(n) { it }其实是IntArray(n){ index -> index }，即：创建了一个数组，数组每个位置上的值为下标的值。

并查集的物理与逻辑实现

可以看到，并查集在物理实现上基于数组或散列表，从逻辑上就是若干棵树组成的森林，每个节点都持有父节点的引用。

3. 并查集的两个操作

并查集使用根节点来代表一个集合，这种方法叫做 代表元法，根节点就是代表元。在此基础上，并查集实现了两个基本操作：合并 & 查询

合并操作
合并操作就是将一个节点的的父节点指向另一个的根节点
查询操作
查询操作就是查询节点的根节点，如果两个节点的根节点相同，那么表示在一个集合中（相连）。

例如，使用Union(x,y)来合并两个节点，而Find(x)查询元素的根节点（代表元）。下面是一个最基本的并查集实现：

private class UnionFind(n: Int) {

    1. 初始时，节点指向自己
    val parent = IntArray(n) { it }

    2. 查询
    fun find(x: Int): Int {
        var key = x
        while (key != parent[key]) {
            key = parent[key]
        }
        return key
    }
    
    3. 合并
    fun union(x: Int, y: Int) {
        val rootX = find(x)
        val rootY = find(y)
        parent[rootY] = rootX 
    }

    4. 判断连通性
    fun isConnected(x: Int, y: Int): Boolean {
        return find(x) == find(y)
    }
}

并查集的合并操作

4. 连通问题 & 路径问题

并查集专注于解决连通问题，即两个元素是否相连，不关心元素之间的路径 & 距离；而路径问题往往需要找出连接两个元素的路径甚至是最短路径，这就超出了并查集的处理范围。

举个例子，给定一系列航班信息，北京——上海，上海——苏州，苏州——杭州，杭州——北京，问是否存在北京到苏州的路径，这就是连通问题，而问北京到苏州的最短路径，这就是路径问题。

关于并查集的 连通分量，表示的是整个并查集中独立的集合（或树）的个数。例如：

private class UnionFind(n: Int) {

    1. 初始时，节点指向自己
    val parent = IntArray(n) { it }

    2. 连通分量计数
    var count = n
    
    3. 合并
    fun union(x: Int, y: Int) {
        val rootX = find(x)
        val rootY = find(y)
        if(rootX == rootY){
            return
        }
        // 合并后，连通分量减一
        parent[rootY] = rootX 
        count -- 
    }
    ...
}

连通分量就是集合个数

5. 并查集的优化

前面说到并查集逻辑上是树的数据结构，既然是树的结构，性能就与树的高度有关。极端情况下，会出现树的高度为 n 的情况（例如 union(6,7).union(5,6)、union(4,5,)、..），此时，查询的复杂度将退化到O(n)

在并查集里，有两类针对树高度的优化：路径压缩 & 按秩合并：

5.1 路径压缩（Path compression）

指在查询的过程中，更改父节点的引用使得树的高度更低，具体分为 隔代压缩 & 完全压缩。

隔代压缩：将父节点指向父节点的父节点

1. 非递归写法
fun find(x: Int): Int {
    var key = x
    while (parent[key] != key) {
        parent[key] = parent[parent[key]] // 关键
        key = parent[key]
    }
    return key
}
-------------------------------------------------------
2. 递归写法
fun find(x: Int): Int {
    var key = x
    if (parent[key] != key) {
        parent[key] = find(parent[key])
    }
    return parent[key] // 关键
}

提示
这里为不熟悉 Kotlin 的同学解释一下，为什么要加 var key = x 呢？因为 Kotlin 中函数形参是不可变变量。

完全压缩：直接将父节点指向根节点

隔代压缩 & 完全压缩

5.2 按秩（Rank）合并

指在合并的过程中，将高度更低的树根节点指向高度更高的根节点，避免合并以后树的高度增加。为了表示树的高度，使用 rank 数组，表示以第 i 个节点为根的树的高度。

class UnionFind(n: Int) {
    1. 根节点的高度
    private val rank = IntArray(n) { 1 }
    2. 查询（未使用路径压缩）
    fun find(x: Int): Int {
        var key = x
        while (key != parent[key]) {
            key = parent[key]
        }
        return key
    }
    3. 按秩合并
    fun union(key1: Int, key2: Int) {
        val root1 = find(key1)
        val root2 = find(key2)

        if(rank[root1] > rank[root2]){
            parent[root2] = root1
        }else if(rank[root2] > rank[root1]){
            parent[root1] = root2
        }else{
            parent[root1] = root2
            rank[root1] ++
            //  或
            //  parent[root2] = root1
            //  rank[root2] ++
        }
    }
}

按秩合并

5.3 小结

需要记住的是：只使用一种优化方式，查询的时间复杂度是 $O(lgn)$ ，如果同时使用路径压缩和按秩合并，查询的时间复杂度接近 $O(1)$ （反阿克德函数），可以说是相当优秀了。通常情况下，路径压缩和按秩合并使用一个即可。

6. 总结

并查集比较冷门，建议应试者合理安排学习时间，在优化并查集时，一般路径压缩和按秩合并使用一个即可。隔代压缩实现简单，也很好记，建议使用。

参考资料

《并查集》 —— LeetCode 出品
《第 12 章并查集》 —— liweiwei 著
《等式方程的可满足性》 —— LeetCode 出品