关于android:如何使用并查集解决朋友圈问题

本文已收录到  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、再遍历所有不等式，判断不等式中的两个变量是否处于同一个子集。是则阐明有抵触，即等式方程不成立。

题解示例如下：

题解

// 未优化版本
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·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. 总结

到这里，并查集的内容就讲完了。文章结尾也提到了，并查集并不算面试中的高频题目，然而它的设计思维的确十分妙。不晓得你有没有这种经验，在看到一种十分美好的解题 / 设计思维后，会不盲目地赞不绝口，直呼外行，并查集就是这种。

更多同类型题目：

参考资料

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