前言

大家好，我是小彭。

今天分享到的是一種相對冷門的數(shù)據(jù)結(jié)構(gòu) —— 并查集。雖然冷門，但是它背后體現(xiàn)的算法思想?yún)s非常精妙，在處理特定問題上能做到出奇制勝。那么，并查集是用來解決什么問題的呢？

學習路線圖：

1. 認識并查集

除了并查集之外，不相交集合（Disjoint Sets）、合并-查找集合（Merge-find Set）、聯(lián)合-查詢數(shù)據(jù)結(jié)構(gòu)（Union-find Data Structure）、聯(lián)合-查詢算法（Union-find algorithm），均表示相同的數(shù)據(jù)結(jié)構(gòu)或思想。

1.1 并查集用于解決什么問題？

并查集是一種用來高效地判斷 “動態(tài)連通性 ” 的數(shù)據(jù)結(jié)構(gòu)： 即給定一個無向圖，要求判斷某兩個元素之間是否存在相連的路徑（連通），這就是連通問題，也叫 “朋友圈” 問題。聽起來有點懵，你先別著急哈，咱來一點一點地把這個知識體系建立起來。

先舉個例子，給定一系列航班信息，問是否存在 “北京” 到 “廣州” 的路徑，這就是連通性問題。而如果是問 “北京” 到 “廣州” 的最短路徑，這就是路徑問題。并查集是專注于解決連通性問題的數(shù)據(jù)結(jié)構(gòu)，而不關(guān)心元素之間的路徑與距離，所以最短路徑等問題就超出了并查集的能夠處理的范圍，不是它考慮的問題。

連通問題與路徑問題示意圖

另一個關(guān)鍵點是，并查集也非常適合處理動態(tài)數(shù)據(jù)的連通性問題。 因為在完成舊數(shù)據(jù)的處理后，舊數(shù)據(jù)的連通關(guān)系是記錄在并查集中的。即使后續(xù)動態(tài)增加新的數(shù)據(jù)，也不需要重新檢索整個數(shù)據(jù)集，只需要將新數(shù)據(jù)提供的信息補充到并查集中，這帶有空間換時間的思想。

動態(tài)連通問題

理解了并查集的應(yīng)用場景后，下面討論并查集是如何解決連通性的問題。

1.2 并查集的邏輯結(jié)構(gòu)

既然要解決連通性問題，那么在并查集的邏輯結(jié)構(gòu)里，就必須用某種方式體現(xiàn)出兩個元素或者一堆元素之間的連接關(guān)系。那它是怎么體現(xiàn)的呢 —— 代表元法。

并查集使用 “代表元法” 來表示元素之間的連接關(guān)系：將相互連通的元素組成一個子集，并從中選取一個元素作為代表元。而判斷兩個元素之間是否連通，就是判斷它們的代表元是否相同，代表元相同則說明處于相同子集，代表元不同則說明處于不同的子集。

例如，我們將航班信息構(gòu)建為并查集的數(shù)據(jù)結(jié)構(gòu)后，就有 “重慶” 和 “北京” 兩個子集。此時，問是否存在 “北京” 到 “廣州” 的路徑，就是看 “北京” 和 “廣州” 的代表元是否相同。可見它們的代表元是相同的，因此它們是連通的。

并查集的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

理解了并查集的邏輯結(jié)構(gòu)后，下面討論如何用代碼實現(xiàn)并查集。

1.3 并查集的物理結(jié)構(gòu)

并查集的物理結(jié)構(gòu)可以是數(shù)組，亦可以是鏈表，只要能夠體現(xiàn)節(jié)點之間連接關(guān)系即可。

• 鏈表實現(xiàn)： 為每個元素創(chuàng)建一個鏈表節(jié)點，每個節(jié)點持有指向父節(jié)點的指針，通過指針的的指向關(guān)系來構(gòu)建集合的連接關(guān)系，而根節(jié)點（代表元）的父節(jié)點指針指向節(jié)點本身；
• 數(shù)組實現(xiàn)： 創(chuàng)建與元素個數(shù)相同大小的數(shù)組，每個數(shù)組下標與每個元素一一對應(yīng)，數(shù)組的值表示父節(jié)點的下標位置，而根節(jié)點（代表元）所處位置的值就是數(shù)組下標，表示指向本身。

數(shù)組實現(xiàn)相對于鏈表實現(xiàn)更加常見，另外，在數(shù)組的基礎(chǔ)上還衍生出散列表的實現(xiàn)，關(guān)鍵看元素個數(shù)是否固定。例如：

• 在 LeetCode · 990. 等式方程的可滿足性 這道題中，節(jié)點是已知的 26 個字母，此時使用數(shù)組即可；
• 在 LeetCode · 684. 冗余連接 這道題中，節(jié)點個數(shù)是未知的，此時使用散列表更合適。

提示： 我們這里將父節(jié)點指向節(jié)點本身定義為根節(jié)點，也有題解將父節(jié)點指向 null 或者 -1 的節(jié)點定義為根節(jié)點。兩種方法都可以，只要能夠區(qū)分出普通節(jié)點和根節(jié)點。但是指向節(jié)點本身的寫法更簡潔，不需要擔心 Union(x, x) 出現(xiàn)死循環(huán)。

以下為基于數(shù)組和基于散列表的代碼模板：

基于數(shù)組的并查集

// 數(shù)組實現(xiàn)適合元素個數(shù)固定的場景
class UnionFind(n: Int) {
    // 創(chuàng)建一個長度為 n 的數(shù)組，每個位置上的值初始化數(shù)組下標，表示初始化時有 n 個子集
    private val parent = IntArray(n) { it }
    ...
}

基于散列表的并查集

// 散列表實現(xiàn)適合元素個數(shù)不固定的場景
class UnionFind() {
    // 創(chuàng)建一個空散列表，
    private val parent = HashMap<Int, Int>()

    // 查詢操作
    fun find(x: Int): Int {
        // 1. parent[x] 為 null 表示首次查詢，先加入散列表中并指向自身
        if (null == parent[x]) {
            parent[x] = x
            return x
        }
        // 下文說明查詢操作細節(jié)...
    }
}

2. 并查集的基本概念

2.1 合并操作與查詢操作

“并查集，并查集”，顧名思義并查集就是由 “并” 和 “查” 這兩個最基本的操作組成的：

• Find 查詢操作： 沿著只用鏈條找到根節(jié)點（代表元）。如果兩個元素的根節(jié)點相同，則說明兩個元素是否屬于同一個子集，否則屬于不同自己；
• Union 合并操作： 將兩個元素的根節(jié)點合并，也表示將兩個子集合并為一個子集。

例如，以下是一個基于數(shù)組的并查集實現(xiàn)，其中使用 Find(x) 查詢元素的根節(jié)點使用 Union(x, y) 合并兩個元素的根節(jié)點：

基于數(shù)組的并查集

class UnionFind(n: Int) {

    // 創(chuàng)建一個長度為 n 的數(shù)組，每個位置上的值初始化數(shù)組下標，表示初始化時有 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. 分別找出兩個元素的根節(jié)點
        val rootX = find(x)
        val rootY = find(y)
        // 2. 任意選擇其中一個根節(jié)點成為另一個根節(jié)點的子樹
        parent[rootY] = rootX
    }

    // 判斷連通性
    fun isConnected(x: Int, y: Int): Boolean {
        // 判斷根節(jié)點是否相同
        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 連通分量

并查集的連通分量，表示的是整個并查集中獨立的子集個數(shù)，也就是森林中樹的個數(shù)。要計算并查集的連通分量，其實就是在合并操作中維護連通分量的計數(shù)，在合并子集后將計數(shù)減一。

class UnionFind(n: Int) {

    private val parent = IntArray(n) { it }

    // 連通分量計數(shù)，初始值為元素個數(shù) n
    var count = n

    // 合并操作
    fun union(x: Int, y: Int) {
        val rootX = find(x)
        val rootY = find(y)
        if(rootX == rootY){
            // 未發(fā)生合并，則不需要減一
            return
        }
        // 合并后，連通分量減一
        parent[rootY] = rootX
        count --
    }
    ...
}

連通分量示意圖

3. 典型例題 · 等式方程的可滿足性

理解以上概念后，就已經(jīng)具備解決連通問題的必要知識了。我們看一道 LeetCode 上的典型例題： LeetCode · 990.

LeetCode 例題

我們可以把每個變量看作一個節(jié)點，而等式表示兩個節(jié)點相連，不等式則表示兩個節(jié)點不相連。那么，我們可以分 2 步：

• 1、先遍歷所有等式，將等式中的兩個變量合并到同一個子集中，最終構(gòu)造一個并查集；
• 2、再遍歷所有不等式，判斷不等式中的兩個變量是否處于同一個子集。是則說明有沖突，即等式方程不成立。

—— 圖片引用自 LeetCode 官方題解

題解示例如下：

題解

// 未優(yōu)化版本
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. 并查集的優(yōu)化

前面說到并查集邏輯上是一種基于森林的數(shù)據(jù)結(jié)構(gòu)。既然與樹有關(guān)，我們自然能想到它的復雜度就與樹的高度有關(guān)。在極端條件下（按照特殊的合并順序），有可能出現(xiàn)樹的高度恰好等于元素個數(shù) n 的情況，此時，單次 Find 查詢操作的時間復雜度就退化到 。

那有沒有優(yōu)化的辦法呢？

4.1 父節(jié)點重要嗎？

在介紹具體的優(yōu)化方法前，我先提出來一個問題：在已經(jīng)選定集合的代表元后，一個元素的父節(jié)點是誰還重要嗎？答案是不重要。

因為無論父節(jié)點是誰，最終都是去找根節(jié)點的。至于中間是經(jīng)過哪些節(jié)點到達根節(jié)點的，這個并不重要。舉個例子，以下 3 個并查集是完全等價的，但明顯第 3 個并查集中樹的高度更低，查詢的時間復雜度更好。

父節(jié)點并不重要

理解了這個點之后，再理解并查集的優(yōu)化策略就容易了。在并查集里，有 2 種防止鏈表化的優(yōu)化策略 —— 路徑壓縮 & 按秩合并。

4.2 路徑壓縮（Path Compression）

路徑壓縮指在查詢的過程中，逐漸調(diào)整父節(jié)點的指向，使其指向更高層的節(jié)點，使得很多深層的階段逐漸放到更靠近根節(jié)點的位置。 根據(jù)調(diào)整的激進程度又分為 2 種：

• 隔代壓縮： 調(diào)整父節(jié)點的指向，使其指向父節(jié)點的父節(jié)點；
• 完全壓縮： 調(diào)整父節(jié)點的指向，使其直接指向根節(jié)點。

路徑壓縮示意圖

路徑壓縮示例程序

// 遍歷寫法
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 節(jié) 提到合并操作時，我們采取的合并操作是相對隨意的。我們在合并時會任意選擇其中一個根節(jié)點成為另一個根節(jié)點的子樹，這就有可能讓一棵較大子樹成為較小子樹的子樹，使得樹的高度增加。

而按秩合并就是要打破這種隨意性，在合并的過程中讓較小的子樹成為較大子樹的子樹，避免合并以后樹的高度增加。 為了表示樹的高度，需要維護使用 rank 數(shù)組，記錄根節(jié)點對應(yīng)的高度。

按秩合并示意圖

按秩合并示例程序

private class UnionFind(n: Int) {
    // 父節(jié)點
    private val parent = IntArray(n) { it }

    // 節(jié)點的高度
    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 優(yōu)化后的時間復雜度分析

在同時使用路徑壓縮和按秩合并兩種優(yōu)化策略時，單次合并操作或查詢操作的時間復雜度幾乎是常量，整體的時間復雜度幾乎是線性的。

以對 N 個元素進行 N - 1 次合并和 M 次查詢的操作序列為例，單次操作的時間復雜度是 ，而整體的時間復雜度是 。其中 是逆阿克曼函數(shù)，是一個增長非常非常慢的函數(shù)，只有使用那些非常大的 “天文數(shù)字” 作為變量 ，否則 的取值都不會超過 4，基本上可以當作常數(shù)。

然而，逆阿克曼函數(shù)畢竟不是常數(shù)，因此我們不能說并查集的時間復雜度是線性的，但也幾乎是線性的。關(guān)于并查集時間復雜度的論證過程，具體可以看參考資料中的兩本算法書籍，我是看不懂的。

5. 典型例題 · 島嶼數(shù)量（二維）

前面我們講的是一維的連通性問題，那么在二維世界里的連通性問題，并查集還依舊好用嗎？我們看 LeetCode 上的另一道典型例題： LeetCode · 200.

LeetCode 例題

這個問題直接上 DFS 廣度搜索自然是可以的：遍歷二維數(shù)組，每找到 1 后使用 DFS 遍歷將所有相連的 1 消除為 0，直到整塊相連的島嶼都消除掉，記錄島嶼數(shù) +1。最后，輸出島嶼數(shù)。

用并查集的來解的話，關(guān)鍵技巧就是建立長度為 M * N 的并查集：遍歷二維數(shù)組，每找到 1 后，將它與右邊和下邊的 1 合并起來，最終輸出并查集中連通分量的個數(shù)，就是島嶼樹。

并查集解法

class Solution {
    fun numIslands(grid: Array<CharArray>): Int {

        // 位置
        fun position(row: Int, column: Int) = row * grid[0].size + column

        // 并查集
        val unionFind = UnionFind(grid)

        // 偏移量數(shù)組（向右和向下）
        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]) {
                    // 消費（避免后續(xù)的遍歷中重復搜索）
                    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>) {

        // 父節(jié)點
        private val parent = IntArray(grid.size * grid[0].size) { it }

        // 節(jié)點高度
        private val rank = IntArray(grid.size * grid[0].size) { 1 }

        // 連通分量（取格子 1 的總數(shù)）
        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) {
                // 未發(fā)生合并，則不需要減一
                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. 總結(jié)

到這里，并查集的內(nèi)容就講完了。文章開頭也提到了，并查集并不算面試中的高頻題目，但是它的設(shè)計思想確實非常妙。不知道你有沒有這種經(jīng)歷，在看到一種非常美妙的解題 / 設(shè)計思想后，會不自覺地拍案叫絕，直呼內(nèi)行，并查集就是這種。

更多同類型題目：

參考資料

• 數(shù)據(jù)結(jié)構(gòu)與算法分析 · Java 語言描述（第 8 章 · 不相互交集類）—— [美] Mark Allen Weiss 著
• 算法導論（第 21 章 · 用于不相交集合的數(shù)據(jù)結(jié)構(gòu)）—— [美] Thomas H. Cormen 等 著
• 專題 · 并查集 —— LeetCode 出品
• 題目 · 等式方程的可滿足性 —— LeetCode 出品