大數據

客戶端用不著的數據結構之并查集

作者 | P.yh

來源 | 五分鐘學算法

什么是并查集

并查集可以看作是一個數據結構,如果你根本沒有聽說過這個數據結構,那么你第一眼看到 “并查集” 這三個字的時候,腦海里會浮現一個什么樣的數據結構呢?

基于我們之前所學的知識來思考并推導一個問題,這相比直接去理解,你會收獲得更多。

我們就來逐字拆解一下,并、查、集 這個三個字,其中前面兩個字都是動詞,第三個字是個名詞。

我們先看名詞,因為只有知道了這個東西是什么,才能去理解它能干什么

集就是集合,我們中學時期就學過這個東西,集合用大白話說就是將一堆元素沒有順序地擺放在同一個地方。

現在我們已經知道了其實并查集本質就是集合,那它能做什么呢?這就要看前兩個字 – “并” 和 “查”,集合的一些操作想必你肯定記得,例如,交集,并集等等,這里的 “并” 其實就指的是并集操作,兩個集合合并后就會變成一個集合,如下所示:

{1,3,5,7} U {2,4,6,8} = {1,2,3,4,5,6,7,8}

那 “查” 又是什么呢?集合本身只是容器,我們最終還是要知道里面存的是什么元素,因此這里的 “查” 是對于集合中存放的元素來說的,我們不僅要查找這個元素在不在集合中,我們還要確定這個元素是在哪個集合中,對于前一個操作,Java 中普通的 set 就可以做到,但是對于后一個操作,僅僅使用一個 set,比較難做到。

好了,現在你應該知道并查集是什么,以及它能干什么了,總結下來就是:

  • 并查集可以進行集合合并的操作(并)
  • 并查集可以查找元素在哪個集合中(查)
  • 并查集維護的是一堆集合(集)

知道了這些后,并查集的概念就清楚了。

并查集的實現

僅僅靠嘴說,還是差點意思,作為程序員,必然是要將我們了解的東西用代碼的形式呈現出來。

相信通過上面的表述,你已經知道,并查集維護的是一堆集合而不是一個集合,用什么樣的數據結構表示并查集?set 嗎?這里有兩個東西我們是必須要知道的,元素的值,集合的標號,一個元素僅可能同時存在于一個集合中,元素對集合是多對一的關系,這么看來我們可以用一個健值對的結構來表示并查集,Map 是肯定可以,但是如果對元素本身沒有特定要求的話,我們可以使用數組,這樣速度更快,使用起來也更加簡單,可以看看下面的例子:

{0},?{1},?{2},?{3},?{4},?{5}?=>?[0,1,2,3,4,5]{0,1,2},?{3,4,5}?=>?[0,0,0,3,3,3]?or?[1,1,1,4,4,4]?...

在解釋上面的數組表示方式之前,不知道你有沒有發現一個事實就是,“元素本身的值是固定不變的,但是元素所屬的集合是可以變化的”,因此我們可以使用數組的 index 來代表元素,數組 index 上存放的值表示元素所屬的集合。

另外一個問題就是,集合怎么表示,標號嗎?最直接的辦法就是就地取材,我們直接從集合中選出一個元素來代表這個集合。相信到這里,你心里還是有存留一堆問題,不急,我們接著看。

說完了集合的表示,我們來看看如何基于這種表示去實現 “并” 和 “查”,也就是集合的合并和元素的查找,這兩個操作是相互影響的,因此最好是放在一起講,合并其實就是改變數組中存放的值,這個值表示的是該元素(index 表示)所在的集合,但是這里有一個問題就是一個集合合并到另一個集合中,我們是不是需要把集合中所有的元素對應的值都更改掉,其實是不需要的,舉個例子你就理解了:

{0,1,2}, {3,4}, {5,6} => [1,1,1,3,3,6,6]
{3,4} U {5,6} => {0,1,2}, {3,4,5,6} => [1,1,1,6,3,6,6]
{0,1,2} U {3,4,5,6} => {0,1,2,3,4,5,6} => [1,6,1,6,3,6,6]

仔細觀察,你會發現每次合并操作,我們僅僅更新了代表元素所對應的集合,并沒有把整個集合里的元素對應的集合都更改了

“代表元素(根元素)” 也就是代表集合的元素,這個元素所在位置存放的就是其本身,兩個集合和并的時候,我們僅僅需要更新代表元素即可,因為查找元素所在集合的過程其實就是查找代表元素的過程,代表元素變了,其余元素對應的集合也就變了。

依據上面合并的例子,我們來看看如何查找:

[1,1,1,3,3,6,6] 查找元素 4 所在集合 4 -> 3, 元素 4 在集合 3 里面
[1,1,1,6,3,6,6] 查找元素 4 所在集合 4 -> 3 -> 6,元素 4 在集合 6 里面
[1,6,1,6,3,6,6] 查找元素 0 所在集合 0 -> 1 -> 6, 元素 0 在集合 6 里面

我們在來看看代碼的實現,首先是查找:

public int find(int element) {
    if (roots[element] == element) {
        return element;
    }

    int father = element;
    while (roots[father] != father) {
        father = roots[father];
    }

    return father;
}

為了讓代碼更加簡潔,我們也可以寫成遞歸的形式:

public int find(int element) {
    if (roots[element] == element) {
        return element;
    }

    return find(roots[element]);
}

查找就是查找代表元素的過程。

另外就是合并,當兩個元素相遇,我們合并是將這兩個元素所在的集合進行合并,因此我們依然要借助 find 找到這兩個元素所在的集合,如果是相同的集合就不需要合并,不同的集合,就將其中一個代表元素進行更改,使其指向另一個代表元素:

public void union(int element1, int element2) {
    int root1 = find(element1);
    int root2 = find(element2);

    if (root1 != root2) {
        roots[root1] = root2;
    }
}

不知道你有沒有思考這個地方為什么數組的名字要命名成 roots,畫畫圖,你會發現并查集其實可以看成是多棵樹,也就是森林,只不過這些樹的邊的方向是從 child 到 parent 的。形象一點解釋就是倒著的樹。

優化 – 路徑壓縮

我們可以分析一下上面的代碼的時間復雜度,上面的兩個函數操作都是基于數組的,其中 union 操作又是依賴于 find 的,因此 find 操作的時間復雜度等同于并查集操作的時間復雜度。首先我們來看一個例子:

{0}, {1}, {2}, {3}, ... {n} => [0,1,2,3,...,n]
{0} U {1} => {1,1,2,3,...,n}
{1} U {2} => {1,2,2,3,...,n}
{2} U {3} => {1,2,3,3,...,n}
...

上面一步步合并,到最后 find(1) 的時間復雜度是 O(n) 的,find 操作的最差時間是 O(n),有沒有辦法優化呢?有一個路徑壓縮的思路,還是上面的例子,上面的例子我們最后得到的是一個長長的搜索鏈:

1?->?2?->?3?->?...?->?n

優化的思路就是讓這個鏈變短,如果我們 find(1) 的話,到最后我們可以找到 “代表元素”,但是從 1 到 “代表元素” 中間的所有元素其實都是同一個集合的,從它們開始 find 也都是找的同一個代表元素,那我們是不是可以將 find(1) 找到的代表元素賦值給中間經過的這些元素呢?這樣下次,從這些元素直接就可以找到代表元素。也就是將上面的鏈變成:

1 -> n
2 -> n
3 -> n
...

find 函數優化后就會是:

public int find(int element) {
    if (root[element] == element) {
        return element;
    }

    // 找到代表元素
    int father = element;
    while (root[father] != father) {
        father = root[father];
    }

    // 將路徑上所有進過的元素都直接指向代表元素
    int compressPointer = element;
    while (root[compressPointer] != father) {
        int tmp = root[compressPointer];
        root[compressPointer] = father;
        compressPointer = tmp;
    }

    return father;
}

寫成遞歸的形式會比較簡潔:

private int find(int element) {
    if (roots[element] == element) {
        return element;
    }

    return roots[element] = find(roots[element]);
}

find 經過路徑壓縮后時間復雜度會變成 O(1),可能你不太理解為什么這里的時間復雜度是 O(1),代碼當中明明就有 while 循環啊。

可以思考一下動態數組的擴容,動態數組就像是 Java 中的 ArrayList 和 C++ 中的 vector,這些動態數組是基于靜態數組實現的,一開始的大小不會太大,如果元素裝滿了,它就會重新開辟一個為原來兩倍大小的靜態數組,然后把之前的值都拷貝到新的數組中,這一步的 add 操作是 O(n) 的,但是將其均攤到前面 n – 1 步 add 操作,時間復雜度還是 O(1)。同樣,思考并查集的時間復雜度的時候也可以往這個方向去想,基于之前的例子 find(1) 一次 O(n) 的操作過后,find(1), find(2), find(3) … 都變成 O(1) 了。

我并不想從數學理論上面去證明,這個非常復雜,有些論文證明說并查集時間復雜度最壞會到 O(logn),也有些論文說時間復雜度是 O(an),這里的 a 是一個極小極小的數,這兩種表示方式都沒有錯,但是并查集退化到 O(logn) 的幾率會非常非常的小,只有非常極端的例子才會出現,僅僅記住一個時間復雜度對于我們理解算法本身并沒有特別大的幫助。

舉個例子,快速排序 作為當今最偉大的 十大算法 之一,我們總說快排的時間復雜度是 O(nlgn),你是否了解過這個算法最差的時間復雜度是 O(n^2) 的,而且不穩定,歸并排序穩定且最差時間復雜度是 O(nlgn),但是相比于快排,還是會遜色不少。

可見分析一個算法的性能還是不能僅僅看最差時間復雜度。

如果我們把前面講到的東西拼接在一起,我們就可以組合成一個真正的并查集結構:

private?class?UnionFind?{????private?int[]?roots;????private?UnionFind(int?size)?{????????this.roots?=?new?int[size];????????for?(int?i?=?0;?i?<?size;?++i)?{????????????roots[i]?=?i;????????}????}????private?int?find(int?element)?{????????if?(roots[element]?==?element)?{????????????return?element;????????}????????return?roots[element]?=?find(roots[element]);????}????private?void?union(int?element1,?int?element2)?{????????int?root1?=?find(element1);????????int?root2?=?find(element2);????????if?(root1?!=?root2)?{????????????roots[root1]?=?root2;????????}????}}

并查集還有一個優化叫做啟發式合并,就是在 union 操作上優化,之前說過并查集可以看作是一堆倒著的樹,這個優化主要是考慮樹的深度,合并的時候需要將深度小的樹連到深度大的樹上面去,因為這個優化對時間的影響并沒有路徑壓縮這么大,因此這里跳過,有興趣可以了解一下,對于一般的問題,使用路徑壓縮就完全夠了。

并查集可以用來解決什么問題

并查集往往用于解決圖上的問題,并查集只有兩個操作,“并” 和 “查”,但是通過這兩個操作可以派生出一些其他的應用:

  • 圖的連通性問題
  • 集合的個數
  • 集合中元素的個數

圖的連通性很好理解,一個圖是不是連通的是指,“如果是連通圖,那么從圖上的任意節點出發,我們可以遍歷到圖上所有的節點”, 這里我們只需要將在圖上的節點放到相同的集合中去,然后去看是不是所有的節點均指向同一個集合即可;

集合的個數就是找代表元素的個數,查找某個集合中元素的個數最簡單的方式就是直接遍歷 roots 數組,然后挨個 find,另外一種方法是在結構中多保存一個數組用來記錄每個集合中元素的個數,并根據具體的操作來更改。

反過來我們也要思考一個問題就是,什么問題是并查集所不能解決的?

并查集的合并操作是不可逆的,你可以理解成只合不分,也就是說兩個集合合并之后就不會再分開來了,另外并查集只會保存并維護集合和元素的關系,至于元素之間的關系,比如圖上節點與節點的邊,這種信息并查集是不會維護的,如果遇到題目讓你分析諸如此類的問題,那么并查集并不是一個好的出發點,你可能需要往其他的算法上去考慮。

以上是這次的分享,希望對你有所幫助。

我還沒有學會寫個人說明!

微盟系統崩潰后續:微商城等核心業務已恢復

上一篇

Nginx 為什么這么快?

下一篇

你也可能喜歡

客戶端用不著的數據結構之并查集

長按儲存圖像,分享給朋友

ITPUB 每周精要將以郵件的形式發放至您的郵箱


微信掃一掃

微信掃一掃
双色球常规走势图 澳洲幸运5平台 黑龙江6+1 2012欧洲杯决赛比分预测 广东十一选五是合法 1分彩计划平台 友乐广西麻将怎么开挂 竞彩比分直播500n 竞彩足球比分旧版下载 十分十一选五开奖走势 排列5走势图500 今日足球比赛比分 黑龙江快乐10分开奖结果正好网