本文已收录到 GitHub AndroidFamily，有 Android 进阶知识系统，欢迎 Star。技能和职场问题，请关注大众号 [彭旭锐] 私信我提问。

前语

大家好，我是小彭。

今日分享到的是一种相对冷门的数据结构 —— 并查集。虽然冷门，可是它背后表现的算法思维却十分精妙，在处理特定问题上能做到出奇制胜。那么，并查集是用来处理什么问题的呢？

---

学习路线图：

---

1. 知道并查集

除了并查集之外，不相交调集（Disjoint Sets）、兼并-查找调集（Merge-find Set）、联合-查询数据结构（Union-find Data Structure）、联合-查询算法（Union-find algorithm），均表明相同的数据结构或思维。

1.1 并查集用于处理什么问题？

并查集是一种用来高效地判别 “动态连通性 ” 的数据结构： 即给定一个无向图，要求判别某两个元素之间是否存在相连的途径（连通），这便是连通问题，也叫 “朋友圈” 问题。听起来有点懵，你先别着急哈，咱来一点一点地把这个知识系统建立起来。

先举个例子，给定一系列航班信息，问是否存在 “北京” 到 “广州” 的途径，这便是连通性问题。而如果是问 “北京” 到 “广州” 的最短途径，这便是途径问题。并查集是专心于处理连通性问题的数据结构，而不关心元素之间的途径与间隔，所以最短途径等问题就超出了并查集的能够处理的范围，不是它考虑的问题。

连通问题与途径问题示意图

另一个要害点是，并查集也十分适宜处理动态数据的连通性问题。 由于在完成旧数据的处理后，旧数据的连通联系是记载在并查会集的。即便后续动态添加新的数据，也不需求重新检索整个数据集，只需求将新数据供给的信息补充到并查会集，这带有空间换时刻的思维。

动态连通问题

了解了并查集的运用场景后，下面评论并查集是如何处理连通性的问题。

1.2 并查集的逻辑结构

已然要处理连通性问题，那么在并查集的逻辑结构里，就必须用某种方式表现出两个元素或许一堆元素之间的衔接联系。那它是怎么表现的呢 —— 代表元法。

并查集运用 “代表元法” 来表明元素之间的衔接联系：将相互连通的元素组成一个子集，并从中选取一个元素作为代表元。而判别两个元素之间是否连通，便是判别它们的代表元是否相同，代表元相同则说明处于相同子集，代表元不同则说明处于不同的子集。

例如，咱们将航班信息构建为并查集的数据结构后，就有 “重庆” 和 “北京” 两个子集。此刻，问是否存在 “北京” 到 “广州” 的途径，便是看 “北京” 和 “广州” 的代表元是否相同。可见它们的代表元是相同的，因而它们是连通的。

并查集的逻辑结构和物理结构

了解了并查集的逻辑结构后，下面评论如何用代码完成并查集。

1.3 并查集的物理结构

并查集的物理结构能够是数组，亦能够是链表，只需能够表现节点之间衔接联系即可。

• 链表完成： 为每个元素创建一个链表节点，每个节点持有指向父节点的指针，通过指针的的指向联系来构建调集的衔接联系，而根节点（代表元）的父节点指针指向节点自身；
• 数组完成： 创建与元素个数相同大小的数组，每个数组下标与每个元素一一对应，数组的值表明父节点的下标方位，而根节点（代表元）所在方位的值便是数组下标，表明指向自身。

数组完成相对于链表完成愈加常见，另外，在数组的基础上还衍生出散列表的完成，要害看元素个数是否固定。例如：

• 在 LeetCode 990. 等式方程的可满意性 这道题中，节点是已知的 26 个字母，此刻运用数组即可；
• 在 LeetCode 684. 冗余衔接 这道题中，节点个数是不知道的，此刻运用散列表更适宜。

提示： 咱们这儿将父节点指向节点自身界说为根节点，也有题解将父节点指向 null 或许 -1 的节点界说为根节点。两种办法都能够，只需能够区分出普通节点和根节点。可是指向节点自身的写法更简练，不需求忧虑 Union(x, x) 呈现死循环。

以下为根据数组和根据散列表的代码模板：

根据数组的并查集

// 数组完成适宜元素个数固定的场景
class UnionFind(n: Int) {
    // 创建一个长度为 n 的数组，每个方位上的值初始化数组下标，表明初始化时有 n 个子集
    private val parent = IntArray(n) { it }
    ...
}

根据散列表的并查集

// 散列表完成适宜元素个数不固定的场景
class UnionFind() {
    // 创建一个空散列表，
    private val parent = HashMap<Int, Int>()
    // 查询操作
    fun find(x: Int): Int {
        // 1. parent[x] 为 null 表明首次查询，先加入散列表中并指向自身
        if (null == parent[x]) {
            parent[x] = x
            return x
        }
        // 下文说明查询操作细节...
    }
}

---

2. 并查集的基本概念

2.1 兼并操作与查询操作

“并查集，并查集”，顾名思义并查集便是由 “并” 和 “查” 这两个最基本的操作组成的：

• Find 查询操作： 沿着只用链条找到根节点（代表元）。如果两个元素的根节点相同，则说明两个元素是否归于同一个子集，否则归于不同自己；
• Union 兼并操作： 将两个元素的根节点兼并，也表明将两个子集兼并为一个子集。

例如，以下是一个根据数组的并查集完成，其间运用 Find(x) 查询元素的根节点运用 Union(x, y) 兼并两个元素的根节点：

根据数组的并查集

class UnionFind(n: Int) {
    // 创建一个长度为 n 的数组，每个方位上的值初始化数组下标，表明初始化时有 n 个子集
    val parent = IntArray(n) { it }
    // 查询操作（遍历写法）
    fun find(x: Int): Int {
        var key = x
        while (key != parent[key]) {
            key = parent[key]
        }
        return key
    }
    // 兼并操作
    fun union(x: Int, y: Int) {
        // 1. 别离找出两个元素的根节点
        val rootX = find(x)
        val rootY = find(y)
        // 2. 恣意挑选其间一个根节点成为另一个根节点的子树
        parent[rootY] = rootX
    }
    // 判别连通性
    fun isConnected(x: Int, y: Int): Boolean {
        // 判别根节点是否相同
        return find(x) == find(y)
    }
    // 查询操作（递归写法）
    fun find(x: Int): Int {
        var key = x
        if (key != parent[key]) {
            return find(parent[key])
        }
        return key
    }
}

兼并与查询示意图

2.2 连通重量

并查集的连通重量，表明的是整个并查会集独立的子集个数，也便是森林中树的个数。要核算并查集的连通重量，其实便是在兼并操作中保护连通重量的计数，在兼并子集后将计数减一。

class UnionFind(n: Int) {
    private val parent = IntArray(n) { it }
    // 连通重量计数，初始值为元素个数 n
    var count = n
    // 兼并操作
    fun union(x: Int, y: Int) {
        val rootX = find(x)
        val rootY = find(y)
        if(rootX == rootY){
            // 未产生兼并，则不需求减一
            return
        }
        // 兼并后，连通重量减一
        parent[rootY] = rootX
        count --
    }
    ...
}

连通重量示意图

---

3. 典型例题 等式方程的可满意性

了解以上概念后，就已经具备处理连通问题的必要知识了。咱们看一道 LeetCode 上的典型例题： LeetCode 990.

LeetCode 例题

咱们能够把每个变量看作看作一个节点，而等式表明两个节点相连，不等式则表明两个节点不相连。那么，咱们能够分 2 步：

• 1、先遍历一切等式，将等式中的两个变量兼并到同一个子会集，终究构造一个并查集；
• 2、再遍历一切不等式，判别不等式中的两个变量是否处于同一个子集。是则说明有冲突，即等式方程不成立。

—— 图片引证自 LeetCode 官方题解

题解示例如下：

题解

// 未优化版本
class Solution {
    fun equationsPossible(equations: Array<String>): Boolean {
        // 26 个小写字母的并查集
        val unionFind = UnionFind(26)
        // 兼并一切等式
        for (equation in equations.filter { it[1] == '=' }) {
            unionFind.union(equation.first(), equation.second())
        }
        // 查看不等式是否与连通性冲突
        for (equation in equations.filter { it[1] == '!' }) {
            if (unionFind.isConnected(equation.first(), equation.second())) {
                return false
            }
        }
        return true
    }
    private fun String.first(): Int {
        return this[0].toInt() - 97
    }
    private fun String.second(): Int {
        return this[3].toInt() - 97
    }
    private class UnionFind() {
        // 代码略
    }
}

---

4. 并查集的优化

前面提到并查集逻辑上是一种根据森林的数据结构。已然与树有关，咱们天然能想到它的复杂度就与树的高度有关。在极点条件下（依照特别的兼并次序），有可能呈现树的高度刚好等于元素个数 n 的状况，此刻，单次 Find 查询操作的时刻复杂度就退化到 $O(n)$。

那有没有优化的办法呢？

4.1 父节点重要吗？

在介绍详细的优化办法前，我先提出来一个问题：在已经选定调集的代表元后，一个元素的父节点是谁还重要吗？答案是不重要。

由于无论父节点是谁，终究都是去找根节点的。至于中间是通过哪些节点抵达根节点的，这个并不重要。举个例子，以下 3 个并查集是完全等价的，但明显第 3 个并查会集树的高度更低，查询的时刻复杂度更好。

父节点并不重要

了解了这个点之后，再了解并查集的优化战略就简单了。在并查集里，有 2 种防止链表化的优化战略 —— 途径紧缩 & 按秩兼并。

4.2 途径紧缩（Path Compression）

途径紧缩指在查询的过程中，逐步调整父节点的指向，使其指向更高层的节点，使得很多深层的阶段逐步放到更接近根节点的方位。 根据调整的急进程度又分为 2 种：

• 隔代紧缩： 调整父节点的指向，使其指向父节点的父节点；
• 完全紧缩： 调整父节点的指向，使其直接指向根节点。

途径紧缩示意图

途径紧缩示例程序

// 遍历写法
fun find(x: Int): Int {
    var key = x
    while (key != parent[key]) {
        parent[key] = parent[parent[key]] 
        key = parent[key]
    }
    return key
}
// 递归写法
fun find(x: Int): Int {
    var key = x
    if (key != parent[key]) {
        parent[key] = find(parent[key])
        return parent[key]
    }
    return key
}

4.3 按秩兼并（Union by Rank）

在 第 2.1 节 提到兼并操作时，咱们采取的兼并操作是相对随意的。咱们在兼并时会恣意挑选其间一个根节点成为另一个根节点的子树，这就有可能让一棵较大子树成为较小子树的子树，使得树的高度添加。

而按秩兼并便是要打破这种随意性，在兼并的过程中让较小的子树成为较大子树的子树，防止兼并今后树的高度添加。 为了表明树的高度，需求保护运用 rank 数组，记载根节点对应的高度。

按秩兼并示意图

按秩兼并示例程序

private class UnionFind(n: Int) {
    // 父节点
    private val parent = IntArray(n) { it }
    // 节点的高度
    private val rank = IntArray(n) { 1 }
    // 连通重量
    var count = n
        private set
    // 查询（途径紧缩）
    fun find(x: Int): Int {
        var key = x
        while (key != parent[key]) {
            parent[key] = parent[parent[key]]
            key = parent[key]
        }
        return key
    }
    // 兼并（按秩兼并）
    fun union(key1: Int, key2: Int) {
        val root1 = find(key1)
        val root2 = find(key2)
        if (root1 == root2) {
            return
        }
        if (rank[root1] > rank[root2]) {
            // root1 的高度更大，让 root2 成为子树，树的高度不变
            parent[root2] = root1
        } else if (rank[root2] > rank[root1]) {
            // root2 的高度更大，让 root1 成为子树，树的高度不变
            parent[root1] = root2
        } else {
            // 高度相同，谁当子树都一样
            parent[root1] = root2
            // root2 的高度加一
            rank[root2]++
            //  或
            //  parent[root2] = root1
            //  rank[root1] ++
        }
        count--
    }
}

4.4 优化后的时刻复杂度剖析

在一起运用途径紧缩和按秩兼并两种优化战略时，单次兼并操作或查询操作的时刻复杂度几乎是常量，全体的时刻复杂度几乎是线性的。

以对 N 个元素进行 N – 1 次兼并和 M 次查询的操作序列为例，单次操作的时刻复杂度是 $O(a(N))$，而全体的时刻复杂度是 $O(M\cdot a(N))$。其间 $a(x)$ 是逆阿克曼函数，是一个增加十分十分慢的函数，只有运用那些十分大的 “天文数字” 作为变量 $x$，否则 $a(x)$ 的取值都不会超越 4，基本上能够当作常数。

然而，逆阿克曼函数毕竟不是常数，因而咱们不能说并查集的时刻复杂度是线性的，但也几乎是线性的。关于并查集时刻复杂度的证明过程，详细能够看参考资料中的两本算法书本，我是看不懂的。

---

5. 典型例题 岛屿数量（二维）

前面咱们讲的是一维的连通性问题，那么在二维世界里的连通性问题，并查集还仍旧好用吗？咱们看 LeetCode 上的另一道典型例题： LeetCode 200.

LeetCode 例题

这个问题直接上 DFS 广度查找天然是能够的：遍历二维数组，每找到 1 后运用 DFS 遍历将一切相连的 1 消除为 0，直到整块相连的岛屿都消除去，记载岛屿数 +1。最后，输出岛屿数。

用并查集的来解的话，要害技巧便是建立长度为 M * N 的并查集：遍历二维数组，每找到 1 后，将它与右边和下边的 1 兼并起来，终究输出并查会集连通重量的个数，便是岛屿树。

并查集解法

class Solution {
    fun numIslands(grid: Array<CharArray>): Int {
        // 方位
        fun position(row: Int, column: Int) = row * grid[0].size + column
        // 并查集
        val unionFind = UnionFind(grid)
        // 偏移量数组（向右和向下）
        val directions = arrayOf(intArrayOf(0, 1), intArrayOf(1, 0))
        // 边界查看
        fun checkBound(row: Int, column: Int): Boolean {
            return (row in grid.indices) and (column in grid[0].indices)
        }
        for (row in grid.indices) {
            for (column in grid[0].indices) {
                if ('1' == grid[row][column]) {
                    // 消费（防止后续的遍历中重复查找）
                    grid[row][column] = '0'
                    for (direction in directions) {
                        val newRow = row + direction[0]
                        val newColumn = column + direction[1]
                        if (checkBound(newRow, newColumn) && '1' == grid[newRow][newColumn]) {
                            unionFind.union(position(newRow, newColumn), position(row, column))
                        }
                    }
                }
            }
        }
        return unionFind.count
    }
    private class UnionFind(grid: Array<CharArray>) {
        // 父节点
        private val parent = IntArray(grid.size * grid[0].size) { it }
        // 节点高度
        private val rank = IntArray(grid.size * grid[0].size) { 1 }
        // 连通重量（取格子 1 的总数）
        var count = grid.let {
            var countOf1 = 0
            for (row in grid.indices) {
                for (column in grid[0].indices) {
                    if ('1' == grid[row][column]) countOf1++
                }
            }
            countOf1
        }
            private set
        // 兼并（按秩兼并）
        fun union(key1: Int, key2: Int) {
            val root1 = find(key1)
            val root2 = find(key2)
            if (root1 == root2) {
                // 未产生兼并，则不需求减一
                return
            }
            if (rank[root1] > rank[root2]) {
                parent[root2] = root1
            } else if (rank[root2] > rank[root1]) {
                parent[root1] = root2
            } else {
                parent[root1] = root2
                rank[root2]++
            }
            // 兼并后，连通重量减一
            count--
        }
        // 查询（运用途径紧缩）
        fun find(x: Int): Int {
            var key = x
            while (key != parent[key]) {
                parent[key] = parent[parent[key]]
                key = parent[key]
            }
            return key
        }
    }
}

---

6. 总结

到这儿，并查集的内容就讲完了。文章开头也提到了，并查集并不算面试中的高频标题，可是它的规划思维确实十分妙。不知道你有没有这种阅历，在看到一种十分美妙的解题 / 规划思维后，会不自觉地拍案叫绝，直呼熟行，并查集便是这种。

更多同类型标题：

并查集	题解
990. 等式方程的可满意性	【题解】
200. 岛屿数量	【题解】
547. 省份数量	【题解】
684. 冗余衔接	【题解】
685. 冗余衔接 II
1319. 连通网络的操作次数	【题解】
399. 除法求值
952. 按公因数核算最大组件大小
130. 被围绕的区域
128. 最长接连序列
721. 账户兼并
765. 情侣牵手

---

参考资料

• 数据结构与算法剖析 Java 言语描述（第 8 章 不相互交集类）—— [美] Mark Allen Weiss 著
• 算法导论（第 21 章 用于不相交调集的数据结构）—— [美] Thomas H. Cormen 等 著
• 专题 并查集 —— LeetCode 出品
• 标题 等式方程的可满意性 —— LeetCode 出品

本文为稀土技能社区首发签约文章，14天内禁止转载，14天后未获授权禁止转载，侵权必究！