淺談算法之最小生成樹Kruskal的Python實現

Posted on by

一、前言

我們先不講算法的原理，也不講一些七七八八的概念，因為對於初學者來說，看到這些術語和概念往往會很頭疼。頭疼也是正常的，因為無端突然出現這麼多信息，都不知道它們是怎麼來的，也不知道這些信息有什麼用，自然就會覺得頭疼。這也是很多人學習算法熱情很高，但是最後又被勸退的原因。

我們先不講什麼叫生成樹，怎麼生成樹，有向圖、無向圖這些，先簡單點，從最基本的內容開始，完整地將這個算法梳理一遍。

二、樹是什麼

首先，我們先來看看最簡單的數據結構——樹。

樹是一個很抽象的數據結構，因為它在自然界當中能找到對應的物體。我們在初學的時候，往往都會根據自然界中真實的樹來理解這個概念。所以在我們的認知當中，往往樹是長這樣的：

上面這張圖就是自然界中樹的抽象，我們很容易理解。但是一般情況下，我們看到的樹結構往往不是這樣的，而是倒過來的。也就是樹根在上，樹葉在下。這樣設計的原因很簡單，沒什麼特別的道理，隻是因為我們在遍歷樹的時候，往往從樹根開始，從樹根往葉子節點出發。所以我們倒過來很容易理解一些，我們把上面的樹倒過來就成瞭這樣：

上面的兩種畫法當然都是正確的，但既然樹可以正著放，也可以倒過來放，我們自然也可以將它伸展開來放。比如下面這張圖，其實也是一棵樹，隻是我們把它畫得不一樣而已。

我們可以想象一下，假如有一隻無形的大手抓住瞭樹根將它“拎起來”，那麼它自然而然就變成瞭上面的樣子。

然後你會發現，如果真的有這樣大手，它不管拎起哪個節點，都會得到一棵樹。也就是說，如果樹根的位置對我們不再重要的話，樹其實就等價於上面這樣的圖。

那麼這樣的圖究竟是什麼圖呢？它有什麼性質呢？所有的圖都能看成是樹嗎？

顯然這三種情況都不是樹，第一種是因為圖中的邊有方向瞭。有瞭方向之後，圖中連通的情況就被破壞瞭。在我們認知當中樹應該是全連通的，就好像自然界中的一隻螞蟻，可以走到樹上任何位置。不能全連通，自然就不是樹。情況2也不對，因為有瞭環，樹是不應該有環的。自然界中的樹是沒有環的，不存在某根樹枝自己繞一圈，同樣，我們邏輯中的樹也是沒有環的，否則我們遞歸訪問永遠也找不到終點。第三種情況也一樣，有些點孤立在外，不能連通，自然也不是樹。

那我們總結一下，就可以回答這個問題。樹是什麼？樹就是可以全連通（無向圖），並且沒有環路的圖。

三、從圖到樹

從剛才的分析當中，我們得到瞭一個很重要的結論，樹的本質就是圖，隻不過是滿足瞭一些特殊性質的圖。這也是為什麼樹的很多算法都會被收納進圖論這個大概念當中。

從全連通和沒有環路這兩個性質出發，我們又可以得到一個很重要的結論，對於一棵擁有n個節點的樹而言，它的邊數是固定的，一定是n-1條邊。如果超過n-1條邊，那麼當中一定存在環路，如果小於n-1條邊，那麼一定存在不連通的部分。但註意，它隻是一個必要條件，不是一個充分條件。也就是說並不是n個點n-1條邊就一定是樹，這很容易構造出反例。

這個結論雖然很簡單，但是很有用處，它可以解決一個由圖轉化成樹的問題。

也就是說當下我們擁有一個復雜圖，我們想要根據這個圖生成能夠連通所有節點的樹，這個時候應該怎麼辦？如果我們沒有上面的性質，會有一點無從下手的感覺。但有瞭這個性質之後，就明確多瞭。我們一共有兩種辦法，第一種辦法是刪減邊，既然是一個復雜圖，說明邊的數量一定超過n-1。那麼我們可以試著刪去一些邊，最後留下一棵樹。第二種做法與之相反，是增加邊。也就是說我們一開始把所有的邊全部撤掉，然後一條一條地往當中添加n-1條邊，讓它變成一棵樹。

我們試著想一下，會發現刪減邊的做法明顯弱於添加邊的方法。原因很簡單，因為我們每一次在刪除邊的時候都面臨是否會破壞樹上連通關系的拷問。比如下圖：

如果我們一旦刪去瞭AB這條邊，那麼一定會破壞整個結構的連通性。我們要判斷連通關系，最好的辦法就是我們先刪除這條邊，然後試著從A點出發，看看能否到達B點。如果可以，那麼則認為這條邊可以刪除。如果圖很大的話，每一次刪除都需要遍歷整張圖，這會帶來巨大的開銷。並且每一次刪除都會改變圖的結構，很難緩存這些結果。

因此，刪除邊的方式並不是不可行，隻是復雜度非常高，正因此，目前比較流行的兩種最小生成樹的算法都是利用的第二種，也就是添加邊的方式實現的。

到這裡，我們就知道瞭，所謂的最小生成樹算法，就是從圖當中挑選出n-1條邊將它轉化成一棵樹的算法。

四、解決生成問題

我們先不考慮邊上帶權重的情況，我們假設所有邊都是等價的，先來看看生成問題怎麼解決，再來進行優化求最小。

如果采用添加邊的方法，面臨的問題和上面類似，當我們選擇一條邊的時候，我們如何判斷這條邊是有必要添加的呢？這個問題需要用到樹的另外一個性質。

由於沒有環路，樹上任意兩點之間的路徑，有且隻有一條。因為如果存在兩點之間的路徑有兩條，那麼必然可以找到一個環路。它的證明很簡單，但是我們很難憑自己想到這個結論。有瞭這個結論，就可以回答上面的那個問題，什麼樣的邊是有必要添加的？也就是兩個點之間不存在通路的時候。如果兩個點之間已經存在通路，那麼當前這條邊就不能添加瞭，否則必然會出現環。如果沒有通路，那麼可以添加。

所以我們要做的就是設計一個算法，可以維護樹上點的連通性。

但是這又帶來瞭一個新的問題，在樹結構當中，連通性是可以傳遞的。兩個點之間連瞭一條邊，並不僅僅是這兩個點連通，而是所有與這兩個點之間連通的點都連通瞭。比如下圖：

這張圖當中A和B連瞭一條邊，這不僅僅是A和B連通，而是左半邊的集合和右半邊集合的連通。所以，雖然A隻是和B連通瞭，但是和C也連通瞭。AC這條邊也一樣不能被加入瞭。也就是說A和B連通，其實是A所在的集合和B所在的集合合並的過程。看到集合的合並，有沒有一點熟悉的感覺？對嘛，上一篇文章當中我們講的並查集算法就是用來解決集合合並和查詢問題的。那麼，顯然可以用並查集來維護圖中這些點集的連通性。

利用並查集算法，問題就很簡單瞭。一開始所有點之間都不連通，那麼所有點單獨是一個集合。如果當前邊連通的兩個點所屬於同一個集合，那麼說明它們之間已經有通路瞭，這條邊不能被添加。否則的話，說明它們不連通，那麼將這條邊連上，並且合並這兩個集合。

於是，我們就解決瞭生成樹這個問題。

五、從生成樹到最小生成樹

接下來，我們為圖中的每條邊加上權重，希望最後得到的樹的所有權重之和最小。

比如，我們有下面這張圖，我們希望生成的樹上所有邊的權重和最小。

觀察一下這張圖上的邊，長短不一。根據貪心算法，我們顯然希望用盡量短的邊來連通樹。所以Kruskal算法的原理非常簡單粗暴，就是對這些邊進行長短排序，依次從短到長遍歷這些邊，然後通過並查集來維護邊是否能夠被添加，直到所有邊都遍歷結束。

可以肯定，這樣生成出來的樹一定是正確的，雖然我們對邊進行瞭排序，但是每條邊依然都有可能會被用上，排序並不會影響算法的可行性。但問題是，這樣貪心出來的結果一定是最優的嗎？

這裡，我們還是使用之前講過的等價判斷方法。我們假設存在兩條長度一樣的邊，那麼我們的決策是否會影響最後的結果呢？

兩個完全相等的邊一共隻有可能出現三種情況，為瞭簡化圖示，我們把一個集合看成是一個點。第一種情況是這兩條邊連通四個不同的集合：

那麼顯然這兩條邊之間並不會引起沖突，所以我們可以都保留。所以這不會引起反例。

第二種情況是這兩條邊連通三個不同的集合：

這種情況和上面一樣，我們可以都要，並不會影響連通情況。所以也不會引起反例。

最後一種是這兩條邊連通的是兩個集合，也就是下面這樣。

在這種情況下，這兩條件之間互相沖突，我們隻能選擇其中的一條。但是顯然，不論我們怎麼選都是一樣的。因為都是連接瞭這兩個連通塊，然後帶來的價值也是一樣的，並不會影響最終的結果。

當我們把所有情況列舉出來之後，我們就可以明確，在這個問題當中貪心法是可行的，並不會引起反例，所以我們可以放心大膽地用。

六、實際問題與代碼實現

明白瞭算法原理之後，我們來看看這個算法的實際問題。其實這個算法在現實當中的使用蠻多的，比如自來水公司要用水管連通所有的小區。而水管是有成本的，那麼顯然自來水公司希望水管的總長度盡量短。比如山裡的村莊通電，要用盡量少的電纜將所有村莊連通，這些類似的問題其實都可以抽象成最小生成樹來解決。當然現實中的問題可能沒有這麼簡單，除瞭考慮成本和連通之外，還需要考慮地形、人文、社會等其他很多因素。

最後，我們試著用代碼來實現一下這個算法。

class DisjointSet:

    def __init__(self, element_num=None):
        self._father = {}
        self._rank = {}
        # 初始化時每個元素單獨成為一個集合
        if element_num is not None:
            for i in range(element_num):
                self.add(i)

    def add(self, x):
        # 添加新集合
        # 如果已經存在則跳過
        if x in self._father:
            return 
        self._father[x] = x
        self._rank[x] = 0

    def _query(self, x):
        # 如果father[x] == x，說明x是樹根
        if self._father[x] == x:
            return x
        self._father[x] = self._query(self._father[x])
        return self._father[x]

    def merge(self, x, y):
        if x not in self._father:
            self.add(x)
        if y not in self._father:
            self.add(y)
        # 查找到兩個元素的樹根
        x = self._query(x)
        y = self._query(y)
        # 如果相等，說明屬於同一個集合
        if x == y:
            return
        # 否則將樹深小的合並到樹根大的上
        if self._rank[x] < self._rank[y]:
            self._father[x] = y
        else:
            self._father[y] = x
            # 如果樹深相等，合並之後樹深+1
            if self._rank[x] == self._rank[y]:
                self._rank[x] += 1

    # 判斷是否屬於同一個集合
    def same(self, x, y):
        return self._query(x) == self._query(y)

# 構造數據
edges = [[1, 2, 7], [2, 3, 8], [2, 4, 9], [1, 4, 5], [3, 5, 5], [2, 5, 7], [4, 5, 15], [4, 6, 6], [5, 6, 8], [6, 7, 11], [5, 7, 9]]

if __name__ == "__main__":
    disjoinset = DisjointSet(8)
    # 根據邊長對邊集排序
    edges = sorted(edges, key=lambda x: x[2])
    res = 0
    for u, v, w in edges:
        if disjoinset.same(u ,v):
            continue
        disjoinset.merge(u, v)
        res += w
    print(res)

其實主要都是利用並查集，我們額外寫的代碼就隻有幾行而已，是不是非常簡單呢？

七、結尾

相信大傢也都感覺到瞭Kruskal算法的原理非常簡單，如果你是順著文章脈絡這樣讀下來，相信一定會有一種順水推舟，一切都自然而然的感覺。也正是因此，它非常符合直覺，也非常容易理解，一旦記住瞭就不容易忘記，即使忘記瞭我們也很容易自己推導出來。這並不是笑話，有一次我在比賽的時候臨時遇到瞭，當時許久不寫Kruskal算法，一時想不起來。憑著僅有的一點印象，硬是在草稿紙上推導瞭一遍算法。

以上就是淺談算法之最小生成樹Kruskal的Python實現的詳細內容，更多關於Python 最小生成樹Kruskal 的資料請關註WalkonNet其它相關文章！

推薦閱讀：