目錄一、前言二、樹是什么三、從圖到樹四、解決生成問題五、從生成樹到最小生成樹六、實(shí)際問題與代碼實(shí)現(xiàn)七、結(jié)尾一、前言

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

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

二、樹是什么

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

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

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

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

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

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

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

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

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

三、從圖到樹

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

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

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

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

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

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

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

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

四、解決生成問題

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

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

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

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

但是這又帶來了一個(gè)新的問題，在樹結(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這條邊也一樣不能被加入了。也就是說A和B連通，其實(shí)是A所在的集合和B所在的集合合并的過程。看到集合的合并，有沒有一點(diǎn)熟悉的感覺？對(duì)嘛，上一篇文章當(dāng)中我們講的并查集算法就是用來解決集合合并和查詢問題的。那么，顯然可以用并查集來維護(hù)圖中這些點(diǎn)集的連通性。

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

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

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

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

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

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

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

這里，我們還是使用之前講過的等價(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è)連通塊，然后帶來的價(jià)值也是一樣的，并不會(huì)影響最終的結(jié)果。

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

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

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

最后，我們?cè)囍么a來實(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)存在則跳過if x in self._father: return self._father[x] = xself._rank[x] = 0 def _query(self, x):# 如果father[x] == x，說明x是樹根if self._father[x] == x: return xself._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è)元素的樹根x = self._query(x)y = self._query(y)# 如果相等，說明屬于同一個(gè)集合if x == y: return# 否則將樹深小的合并到樹根大的上if self._rank[x] < self._rank[y]: self._father[x] = yelse: self._father[y] = x # 如果樹深相等，合并之后樹深+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): continuedisjoinset.merge(u, v)res += w print(res)

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

七、結(jié)尾

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

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