图论（八）最小生成树
一個(gè)正在進(jìn)行信息化建設(shè)的國(guó)家級(jí)貧困縣，需要在下屬9個(gè)鄉(xiāng)鎮(zhèn)之間架設(shè)光纖網(wǎng)絡(luò)。為減少建設(shè)難度，光纖網(wǎng)主要沿著這9個(gè)鄉(xiāng)鎮(zhèn)之間互連的公路進(jìn)行鋪設(shè)。這9個(gè)鄉(xiāng)鎮(zhèn)之間的公路網(wǎng)以及相互之間的距離(單位：km)如下圖所示：
如果你是工程師，該怎樣設(shè)計(jì)線路鋪設(shè)方案？當(dāng)然，你可以直接把所有的公路網(wǎng)都鋪設(shè)上光纜，這樣的線路總長(zhǎng)度是247公里。但如果你是這樣想的，那么我一定會(huì)懷疑你到底是不是一名工程師！
你可以再設(shè)計(jì)一種方案，如下圖中粗線條所示：
這種鋪設(shè)方案的線路總長(zhǎng)是161公里，這比前面的強(qiáng)多了。再進(jìn)一步，你還可以得到2種更短的鋪設(shè)線路：
這2種線路的總長(zhǎng)分別是100km和95km。顯然比前面的方案節(jié)省了更多。當(dāng)然，這種線路方案你還可以列出很多。
在這個(gè)實(shí)際應(yīng)用中，我們的目的，是要尋求一種連接圖中所有節(jié)點(diǎn)的、成本最低的方式。本質(zhì)上，再抽象一層，這是個(gè)組合優(yōu)化問(wèn)題，可以使用一些智能優(yōu)化算法來(lái)解決。而在這個(gè)實(shí)例上，我們尋求使用更簡(jiǎn)單的圖論方式解決。
當(dāng)然，這是個(gè)老問(wèn)題了，至少在20世紀(jì)初就已經(jīng)提出了，它的解決方案最初是1926年由捷克數(shù)學(xué)家在構(gòu)建一個(gè)電力網(wǎng)絡(luò)的過(guò)程中首先提出來(lái)的。這種方式經(jīng)常被用于架設(shè)電網(wǎng)、通信網(wǎng)、公路網(wǎng)、鐵路網(wǎng)，甚至是架構(gòu)某種形式的計(jì)算集群（這些任務(wù)都需要我們連接其中的每一個(gè)節(jié)點(diǎn)），也是解決旅行商問(wèn)題的基礎(chǔ)。
再回到這個(gè)問(wèn)題本身，要包含圖中所有的頂點(diǎn)n，同時(shí)代價(jià)最少，第一個(gè)想到的自然是減少邊的數(shù)量，而要連接所有n個(gè)頂點(diǎn)，顯然至少需要n-1條邊。而我們知道一顆樹(shù)(tree)就是n個(gè)頂點(diǎn)，n-1條邊。
所以，這里引申出圖論中的一個(gè)新概念：生成樹(shù)(spanning tree)。含有圖中全部n個(gè)頂點(diǎn)，以及包含圖中某些n-1條邊的一顆樹(shù)是該圖的生成樹(shù)。有幾個(gè)情況需要注意：
- 圖本身必須是無(wú)向連通圖；
如果是非連通圖，那就不存在生成樹(shù)的概念。我們知道樹(shù)中任意2點(diǎn)都是連通的。如果是有向圖，那也沒(méi)有這個(gè)概念。 - 生成樹(shù)不止一種；
生成樹(shù)的n-1條邊可以在圖的邊集合中選擇，當(dāng)然不止一種情況。 - 每個(gè)生成樹(shù)代價(jià)不同。
一般使用生成樹(shù)中邊的權(quán)重值總和代表每個(gè)生成樹(shù)的代價(jià)。
而我們的工作就是要找到所有生成樹(shù)中代價(jià)最小的，這就是最小生成樹(shù)(minimum spanning tree)問(wèn)題。
那么，我們構(gòu)建最小生成樹(shù)的時(shí)候，要從哪里著手呢？
首先，我們從邊出發(fā)，先找到最短的邊。
如上圖所示，邊e-i顯然是最短的。最小生成樹(shù)會(huì)不會(huì)一定包含這條邊？根據(jù)上面的描述，生成樹(shù)要包含所有的頂點(diǎn)，因此，生成樹(shù)一定包含e，i兩個(gè)頂點(diǎn)，所以也必然包含一條e，i之間的路徑。我們隨便構(gòu)成一個(gè)生成樹(shù)，見(jiàn)下圖：
圖中粗線條為構(gòu)成的生成樹(shù)，并不包含最短邊e-i。e,i之間的路徑是e-f-j-d-b-a-i，如果我們將邊e-i加入這個(gè)生成樹(shù)，必然構(gòu)成環(huán)。
要消除這個(gè)環(huán)，從而構(gòu)成新的生成樹(shù)，我們可以移除e-f-j-d-b-a-i-e環(huán)路上除邊e-i的其他任意一條邊。例如，移除a-b或b-d。我們看看移除b-d，構(gòu)成了一個(gè)新的生成樹(shù)。
這個(gè)新的生成樹(shù)與原先的生成樹(shù)就差在一個(gè)包含邊b-d，不包含邊e-i，一個(gè)包含邊e-i，不包含b-d。而新的生成樹(shù)代價(jià)比原先的生成樹(shù)代價(jià)低，因?yàn)檫卐-i是最短的，代價(jià)比邊b-d要小。
因此，無(wú)論移除其他邊中的哪條邊，重新構(gòu)成新的生成樹(shù)都比最先的生成樹(shù)代價(jià)小。因?yàn)槟臈l邊的代價(jià)都比邊e-i的代價(jià)要大。也就是說(shuō)，任何不包含最短邊的生成樹(shù)結(jié)構(gòu)都可以被做的更小。所以，最小生成樹(shù)一定包含最短邊。（后面的文章我們將看到，這也是最小生成樹(shù)算法Kruskal的基本思想）。
其次，我們從頂點(diǎn)出發(fā)，來(lái)看看有什么新的結(jié)論。還是上面的圖，我們以頂點(diǎn)b為例，根據(jù)生成樹(shù)的定義，頂點(diǎn)b與其它頂點(diǎn)肯定是連通的。而頂點(diǎn)b有2條邊，即邊a-b，邊b-d。這意味著最小生成樹(shù)必然包含這2條邊中的一個(gè)。而邊b-d比a-b要短，因此選擇b-d是否更合理？
我們用反證法證明下，假設(shè)選擇較長(zhǎng)的邊a-b是更好的選擇，即最小生成樹(shù)包含a-b這條邊。我們把邊b-d也加入這個(gè)生成樹(shù)，形成了一個(gè)環(huán)。在這個(gè)環(huán)中，如果移除邊a-b，那么得到的新生成樹(shù)代價(jià)比以前的要小，這與假設(shè)的選擇較長(zhǎng)邊更好相矛盾。所以在b點(diǎn)選擇較短的邊才有可能生成最小生成樹(shù)。（后面的文章我們將看到，這也是最小生成樹(shù)算法Prim的基本思想）。
參考文獻(xiàn)：
1.《大話數(shù)據(jù)結(jié)構(gòu)》 程杰 清華大學(xué)出版社
2.《Python算法教程》Magnus Lie Hetland 人民郵電出版社
總結(jié)
以上是生活随笔為你收集整理的图论（八）最小生成树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 高考与机器学习训练测试
- 下一篇： 图论（九）最小生成树-Kruskal算法