一、前言

我們先不講算法的原理，也不講一些七七八八的概念，因?yàn)閷?duì)于初學(xué)者來(lái)說(shuō)，看到這些術(shù)語(yǔ)和概念往往會(huì)很頭疼。頭疼也是正常的，因?yàn)闊o(wú)端突然出現(xiàn)這么多信息，都不知道它們是怎么來(lái)的，也不知道這些信息有什么用，自然就會(huì)覺(jué)得頭疼。這也是很多人學(xué)習(xí)算法熱情很高，但是最后又被勸退的原因。

我們先不講什么叫生成樹(shù)，怎么生成樹(shù)，有向圖、無(wú)向圖這些，先簡(jiǎn)單點(diǎn)，從最基本的內(nèi)容開(kāi)始，完整地將這個(gè)算法梳理一遍。

二、樹(shù)是什么

首先，我們先來(lái)看看最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)——樹(shù)。

樹(shù)是一個(gè)很抽象的數(shù)據(jù)結(jié)構(gòu)，因?yàn)樗谧匀唤绠?dāng)中能找到對(duì)應(yīng)的物體。我們?cè)诔鯇W(xué)的時(shí)候，往往都會(huì)根據(jù)自然界中真實(shí)的樹(shù)來(lái)理解這個(gè)概念。所以在我們的認(rèn)知當(dāng)中，往往樹(shù)是長(zhǎng)這樣的：

上面這張圖就是自然界中樹(shù)的抽象，我們很容易理解。但是一般情況下，我們看到的樹(shù)結(jié)構(gòu)往往不是這樣的，而是倒過(guò)來(lái)的。也就是樹(shù)根在上，樹(shù)葉在下。這樣設(shè)計(jì)的原因很簡(jiǎn)單，沒(méi)什么特別的道理，只是因?yàn)槲覀冊(cè)诒闅v樹(shù)的時(shí)候，往往從樹(shù)根開(kāi)始，從樹(shù)根往葉子節(jié)點(diǎn)出發(fā)。所以我們倒過(guò)來(lái)很容易理解一些，我們把上面的樹(shù)倒過(guò)來(lái)就成了這樣：

上面的兩種畫(huà)法當(dāng)然都是正確的，但既然樹(shù)可以正著放，也可以倒過(guò)來(lái)放，我們自然也可以將它伸展開(kāi)來(lái)放。比如下面這張圖，其實(shí)也是一棵樹(shù)，只是我們把它畫(huà)得不一樣而已。

我們可以想象一下，假如有一只無(wú)形的大手抓住了樹(shù)根將它“拎起來(lái)”，那么它自然而然就變成了上面的樣子。

然后你會(huì)發(fā)現(xiàn)，如果真的有這樣大手，它不管拎起哪個(gè)節(jié)點(diǎn)，都會(huì)得到一棵樹(shù)。也就是說(shuō)，如果樹(shù)根的位置對(duì)我們不再重要的話，樹(shù)其實(shí)就等價(jià)于上面這樣的圖。

那么這樣的圖究竟是什么圖呢？它有什么性質(zhì)呢？所有的圖都能看成是樹(shù)嗎？

顯然這三種情況都不是樹(shù)，第一種是因?yàn)閳D中的邊有方向了。有了方向之后，圖中連通的情況就被破壞了。在我們認(rèn)知當(dāng)中樹(shù)應(yīng)該是全連通的，就好像自然界中的一只螞蟻，可以走到樹(shù)上任何位置。不能全連通，自然就不是樹(shù)。情況2也不對(duì)，因?yàn)橛辛谁h(huán)，樹(shù)是不應(yīng)該有環(huán)的。自然界中的樹(shù)是沒(méi)有環(huán)的，不存在某根樹(shù)枝自己繞一圈，同樣，我們邏輯中的樹(shù)也是沒(méi)有環(huán)的，否則我們遞歸訪問(wèn)永遠(yuǎn)也找不到終點(diǎn)。第三種情況也一樣，有些點(diǎn)孤立在外，不能連通，自然也不是樹(shù)。

那我們總結(jié)一下，就可以回答這個(gè)問(wèn)題。樹(shù)是什么？樹(shù)就是可以全連通（無(wú)向圖），并且沒(méi)有環(huán)路的圖。

三、從圖到樹(shù)

從剛才的分析當(dāng)中，我們得到了一個(gè)很重要的結(jié)論，樹(shù)的本質(zhì)就是圖，只不過(guò)是滿足了一些特殊性質(zhì)的圖。這也是為什么樹(shù)的很多算法都會(huì)被收納進(jìn)圖論這個(gè)大概念當(dāng)中。

從全連通和沒(méi)有環(huán)路這兩個(gè)性質(zhì)出發(fā)，我們又可以得到一個(gè)很重要的結(jié)論，對(duì)于一棵擁有n個(gè)節(jié)點(diǎn)的樹(shù)而言，它的邊數(shù)是固定的，一定是n-1條邊。如果超過(guò)n-1條邊，那么當(dāng)中一定存在環(huán)路，如果小于n-1條邊，那么一定存在不連通的部分。但注意，它只是一個(gè)必要條件，不是一個(gè)充分條件。也就是說(shuō)并不是n個(gè)點(diǎn)n-1條邊就一定是樹(shù)，這很容易構(gòu)造出反例。

這個(gè)結(jié)論雖然很簡(jiǎn)單，但是很有用處，它可以解決一個(gè)由圖轉(zhuǎn)化成樹(shù)的問(wèn)題。

也就是說(shuō)當(dāng)下我們擁有一個(gè)復(fù)雜圖，我們想要根據(jù)這個(gè)圖生成能夠連通所有節(jié)點(diǎn)的樹(shù)，這個(gè)時(shí)候應(yīng)該怎么辦？如果我們沒(méi)有上面的性質(zhì)，會(huì)有一點(diǎn)無(wú)從下手的感覺(jué)。但有了這個(gè)性質(zhì)之后，就明確多了。我們一共有兩種辦法，第一種辦法是刪減邊，既然是一個(gè)復(fù)雜圖，說(shuō)明邊的數(shù)量一定超過(guò)n-1。那么我們可以試著刪去一些邊，最后留下一棵樹(shù)。第二種做法與之相反，是增加邊。也就是說(shuō)我們一開(kāi)始把所有的邊全部撤掉，然后一條一條地往當(dāng)中添加n-1條邊，讓它變成一棵樹(shù)。

我們?cè)囍胍幌?，?huì)發(fā)現(xiàn)刪減邊的做法明顯弱于添加邊的方法。原因很簡(jiǎn)單，因?yàn)槲覀兠恳淮卧趧h除邊的時(shí)候都面臨是否會(huì)破壞樹(shù)上連通關(guān)系的拷問(wèn)。比如下圖：

如果我們一旦刪去了AB這條邊，那么一定會(huì)破壞整個(gè)結(jié)構(gòu)的連通性。我們要判斷連通關(guān)系，最好的辦法就是我們先刪除這條邊，然后試著從A點(diǎn)出發(fā)，看看能否到達(dá)B點(diǎn)。如果可以，那么則認(rèn)為這條邊可以刪除。如果圖很大的話，每一次刪除都需要遍歷整張圖，這會(huì)帶來(lái)巨大的開(kāi)銷。并且每一次刪除都會(huì)改變圖的結(jié)構(gòu)，很難緩存這些結(jié)果。

因此，刪除邊的方式并不是不可行，只是復(fù)雜度非常高，正因此，目前比較流行的兩種最小生成樹(shù)的算法都是利用的第二種，也就是添加邊的方式實(shí)現(xiàn)的。

到這里，我們就知道了，所謂的最小生成樹(shù)算法，就是從圖當(dāng)中挑選出n-1條邊將它轉(zhuǎn)化成一棵樹(shù)的算法。

四、解決生成問(wèn)題

我們先不考慮邊上帶權(quán)重的情況，我們假設(shè)所有邊都是等價(jià)的，先來(lái)看看生成問(wèn)題怎么解決，再來(lái)進(jìn)行優(yōu)化求最小。

如果采用添加邊的方法，面臨的問(wèn)題和上面類似，當(dāng)我們選擇一條邊的時(shí)候，我們?nèi)绾闻袛噙@條邊是有必要添加的呢？這個(gè)問(wèn)題需要用到樹(shù)的另外一個(gè)性質(zhì)。

由于沒(méi)有環(huán)路，樹(shù)上任意兩點(diǎn)之間的路徑，有且只有一條。因?yàn)槿绻嬖趦牲c(diǎn)之間的路徑有兩條，那么必然可以找到一個(gè)環(huán)路。它的證明很簡(jiǎn)單，但是我們很難憑自己想到這個(gè)結(jié)論。有了這個(gè)結(jié)論，就可以回答上面的那個(gè)問(wèn)題，什么樣的邊是有必要添加的？也就是兩個(gè)點(diǎn)之間不存在通路的時(shí)候。如果兩個(gè)點(diǎn)之間已經(jīng)存在通路，那么當(dāng)前這條邊就不能添加了，否則必然會(huì)出現(xiàn)環(huán)。如果沒(méi)有通路，那么可以添加。

所以我們要做的就是設(shè)計(jì)一個(gè)算法，可以維護(hù)樹(shù)上點(diǎn)的連通性。

但是這又帶來(lái)了一個(gè)新的問(wèn)題，在樹(shù)結(jié)構(gòu)當(dāng)中，連通性是可以傳遞的。兩個(gè)點(diǎn)之間連了一條邊，并不僅僅是這兩個(gè)點(diǎn)連通，而是所有與這兩個(gè)點(diǎn)之間連通的點(diǎn)都連通了。比如下圖：

這張圖當(dāng)中A和B連了一條邊，這不僅僅是A和B連通，而是左半邊的集合和右半邊集合的連通。所以，雖然A只是和B連通了，但是和C也連通了。AC這條邊也一樣不能被加入了。也就是說(shuō)A和B連通，其實(shí)是A所在的集合和B所在的集合合并的過(guò)程?？吹郊系暮喜?，有沒(méi)有一點(diǎn)熟悉的感覺(jué)？對(duì)嘛，上一篇文章當(dāng)中我們講的并查集算法就是用來(lái)解決集合合并和查詢問(wèn)題的。那么，顯然可以用并查集來(lái)維護(hù)圖中這些點(diǎn)集的連通性。

利用并查集算法，問(wèn)題就很簡(jiǎn)單了。一開(kāi)始所有點(diǎn)之間都不連通，那么所有點(diǎn)單獨(dú)是一個(gè)集合。如果當(dāng)前邊連通的兩個(gè)點(diǎn)所屬于同一個(gè)集合，那么說(shuō)明它們之間已經(jīng)有通路了，這條邊不能被添加。否則的話，說(shuō)明它們不連通，那么將這條邊連上，并且合并這兩個(gè)集合。

于是，我們就解決了生成樹(shù)這個(gè)問(wèn)題。

五、從生成樹(shù)到最小生成樹(shù)

接下來(lái)，我們?yōu)閳D中的每條邊加上權(quán)重，希望最后得到的樹(shù)的所有權(quán)重之和最小。

比如，我們有下面這張圖，我們希望生成的樹(shù)上所有邊的權(quán)重和最小。

觀察一下這張圖上的邊，長(zhǎng)短不一。根據(jù)貪心算法，我們顯然希望用盡量短的邊來(lái)連通樹(shù)。所以Kruskal算法的原理非常簡(jiǎn)單粗暴，就是對(duì)這些邊進(jìn)行長(zhǎng)短排序，依次從短到長(zhǎng)遍歷這些邊，然后通過(guò)并查集來(lái)維護(hù)邊是否能夠被添加，直到所有邊都遍歷結(jié)束。

可以肯定，這樣生成出來(lái)的樹(shù)一定是正確的，雖然我們對(duì)邊進(jìn)行了排序，但是每條邊依然都有可能會(huì)被用上，排序并不會(huì)影響算法的可行性。但問(wèn)題是，這樣貪心出來(lái)的結(jié)果一定是最優(yōu)的嗎？

這里，我們還是使用之前講過(guò)的等價(jià)判斷方法。我們假設(shè)存在兩條長(zhǎng)度一樣的邊，那么我們的決策是否會(huì)影響最后的結(jié)果呢？

兩個(gè)完全相等的邊一共只有可能出現(xiàn)三種情況，為了簡(jiǎn)化圖示，我們把一個(gè)集合看成是一個(gè)點(diǎn)。第一種情況是這兩條邊連通四個(gè)不同的集合：

那么顯然這兩條邊之間并不會(huì)引起沖突，所以我們可以都保留。所以這不會(huì)引起反例。

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

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

最后一種是這兩條邊連通的是兩個(gè)集合，也就是下面這樣。

在這種情況下，這兩條件之間互相沖突，我們只能選擇其中的一條。但是顯然，不論我們?cè)趺催x都是一樣的。因?yàn)槎际沁B接了這兩個(gè)連通塊，然后帶來(lái)的價(jià)值也是一樣的，并不會(huì)影響最終的結(jié)果。

當(dāng)我們把所有情況列舉出來(lái)之后，我們就可以明確，在這個(gè)問(wèn)題當(dāng)中貪心法是可行的，并不會(huì)引起反例，所以我們可以放心大膽地用。

六、實(shí)際問(wèn)題與代碼實(shí)現(xiàn)

明白了算法原理之后，我們來(lái)看看這個(gè)算法的實(shí)際問(wèn)題。其實(shí)這個(gè)算法在現(xiàn)實(shí)當(dāng)中的使用蠻多的，比如自來(lái)水公司要用水管連通所有的小區(qū)。而水管是有成本的，那么顯然自來(lái)水公司希望水管的總長(zhǎng)度盡量短。比如山里的村莊通電，要用盡量少的電纜將所有村莊連通，這些類似的問(wèn)題其實(shí)都可以抽象成最小生成樹(shù)來(lái)解決。當(dāng)然現(xiàn)實(shí)中的問(wèn)題可能沒(méi)有這么簡(jiǎn)單，除了考慮成本和連通之外，還需要考慮地形、人文、社會(huì)等其他很多因素。

最后，我們?cè)囍么a來(lái)實(shí)現(xiàn)一下這個(gè)算法。

class DisjointSet:

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

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

    def _query(self, x):
        # 如果father[x] == x，說(shuō)明x是樹(shù)根
        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)
        # 查找到兩個(gè)元素的樹(shù)根
        x = self._query(x)
        y = self._query(y)
        # 如果相等，說(shuō)明屬于同一個(gè)集合
        if x == y:
            return
        # 否則將樹(shù)深小的合并到樹(shù)根大的上
        if self._rank[x]  self._rank[y]:
            self._father[x] = y
        else:
            self._father[y] = x
            # 如果樹(shù)深相等，合并之后樹(shù)深+1
            if self._rank[x] == self._rank[y]:
                self._rank[x] += 1

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

# 構(gòu)造數(shù)據(jù)
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)
    # 根據(jù)邊長(zhǎng)對(duì)邊集排序
    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)

其實(shí)主要都是利用并查集，我們額外寫的代碼就只有幾行而已，是不是非常簡(jiǎn)單呢？

七、結(jié)尾

相信大家也都感覺(jué)到了Kruskal算法的原理非常簡(jiǎn)單，如果你是順著文章脈絡(luò)這樣讀下來(lái)，相信一定會(huì)有一種順?biāo)浦郏磺卸甲匀欢坏母杏X(jué)。也正是因此，它非常符合直覺(jué)，也非常容易理解，一旦記住了就不容易忘記，即使忘記了我們也很容易自己推導(dǎo)出來(lái)。這并不是笑話，有一次我在比賽的時(shí)候臨時(shí)遇到了，當(dāng)時(shí)許久不寫Kruskal算法，一時(shí)想不起來(lái)。憑著僅有的一點(diǎn)印象，硬是在草稿紙上推導(dǎo)了一遍算法。

以上就是淺談算法之最小生成樹(shù)Kruskal的Python實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于Python 最小生成樹(shù)Kruskal 的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！