最小生成樹

最小生成樹（英語：Minimum spanning tree，簡稱MST）是最小權重生成樹（英語：Minimum weight spanning tree）的簡稱，是一個連通加權無向圖中一棵權值最小的生成樹。

一個平面圖和它的最小生成樹。在該圖中，邊的長度正比於權值A。

在一給定的無向圖 ${\displaystyle G=(V,E)}$ 中，${\displaystyle (u,v)}$ 代表連接頂點 u 與頂點 v 的邊（即 ${\displaystyle (u,v)\in E}$），而 ${\displaystyle w(u,v)}$ 代表此邊的權重，若存在 T 為 E 的子集（即 ${\displaystyle T\subseteq E}$）且 (V, T) 為樹，使得：

${\displaystyle w(T)=\sum _{(u,v)\in T}w(u,v)}$

的 w(T) 最小，則此 T 為 G 的最小生成樹。

一個連通圖可能有多個生成樹。當圖中的邊具有權值時，總會有一個生成樹的邊的權值之和小於或者等於其它生成樹的邊的權值之和。廣義上而言，對於非連通無向圖來說，它的每一連通分量同樣有最小生成樹，它們的並被稱為最小生成森林。

以有線電視電纜的架設為例，若只能沿著街道佈線，則以街道為邊，而路口為頂點，其中必然有一最小生成樹能使佈線成本最低。

相關性質

存在個數

這張圖表明一個圖中可能有多個最小生成樹

最小生成樹在一些情況下可能會有多個。例如，當圖的每一條邊的權值都相同時，該圖的所有生成樹都是最小生成樹。

唯一性

如果圖的每一條邊的權值都互不相同，那麼最小生成樹將只有一個^[1]。這一定理同樣適用於最小生成森林。

證明：

假設圖${\displaystyle G}$為每條邊權值互不相同的連通圖，且有兩個不同的最小生成樹${\displaystyle T}$和${\displaystyle T'}$。

則${\displaystyle T}$中必然存在一些在${\displaystyle T'}$中並不存在的邊，取其中一條這樣的邊${\displaystyle e_{0}}$。

因為${\displaystyle T'}$是最小生成樹，所以若往${\displaystyle T'}$中添加邊${\displaystyle e_{0}}$，則將會出現環路。（因為有${\displaystyle m}$個頂點的樹有且僅有${\displaystyle m-1}$條邊）

同時可知，如果從${\displaystyle T}$中刪除邊${\displaystyle e_{0}}$，則${\displaystyle T}$將分為互不連通的兩個連通分量。因為${\displaystyle e_{0}\notin T'}$，所以${\displaystyle T'}$中必然有其他的邊連接這兩個連通分量。且將${\displaystyle e_{0}}$加入${\displaystyle T'}$後形成的環路中，除了${\displaystyle e_{0}}$外至少有另一條連接${\displaystyle T}$中刪除${\displaystyle e_{0}}$後的這兩個連通分量的邊。取其中一條這樣的邊，記作${\displaystyle {e_{0}}'}$。此時若將${\displaystyle {e_{0}}'}$加入${\displaystyle T}$，則可連接從${\displaystyle T}$中刪除${\displaystyle e_{0}}$後得到的兩個連通分量，並形成一棵不同的生成樹。

因為${\displaystyle G}$中所有邊的權值互不相同，所以關於${\displaystyle e_{0}}$和${\displaystyle {e_{0}}'}$的權重大小關係，可能有以下兩種情況之一：

1. 若${\displaystyle e_{0}<{e_{0}}'}$，則可從${\displaystyle T'}$中刪除${\displaystyle {e_{0}}'}$並加入${\displaystyle e_{0}}$，從而得到一棵總權值更小的生成樹。這和${\displaystyle T'}$是最小生成樹相矛盾。
2. 若${\displaystyle e_{0}>{e_{0}}'}$，則可從${\displaystyle T}$中刪除${\displaystyle e_{0}}$並加入${\displaystyle {e_{0}}'}$，從而得到一棵總權值更小的生成樹。同樣，這和${\displaystyle T}$是最小生成樹相矛盾。

綜上，若${\displaystyle G}$各邊權重互不相等，則不可能存在兩棵互不相同的最小生成樹。即${\displaystyle G}$的最小生成樹是唯一的。

邊的權值之和最低的子圖

如果圖的邊的權值都為正數，那麼最小生成樹就是該圖的所有包含所有頂點的子圖中權值最低的連通子圖。

環定理

對於連通圖中的任意一個環${\displaystyle C}$：如果${\displaystyle C}$中有邊${\displaystyle e}$的權值大於該環中任意一個其它的邊的權值，那麼這個邊不會是最小生成樹中的邊

證明：
假設${\displaystyle e}$屬於最小生成樹${\displaystyle T1}$，那麼將${\displaystyle e}$刪去將會使得${\displaystyle T1}$變為兩個樹。因為環${\displaystyle C}$必然還存在另一橫切邊ｆ可以連接兩個子樹形成生成樹${\displaystyle T2}$，且由於${\displaystyle f}$＜${\displaystyle e}$，生成樹${\displaystyle T2}$權值更小，與${\displaystyle T1}$是最小生成樹矛盾。

割定理

此圖展示了最小生成樹的割定理。${\displaystyle T}$是該圖唯一的最小生成樹，令${\displaystyle S=\left\{A,B,D,E\right\}}$，則${\displaystyle V-S=\left\{C,F\right\}}$，這樣就形成了一個割，其割集包含3條割邊，即BC，EC，EF，如果去除它們就可以將這兩個子圖完全斷開。在割集中，${\displaystyle e}$是權值最小的邊，所以${\displaystyle S\cup \left\{e\right\}}$是最小生成樹${\displaystyle T}$的一部分。

在一幅連通加權無向圖中，給定任意的割，如有一條割邊的權值嚴格小於所有其他割邊，則這條邊必然屬於圖的最小生成樹。

證明：
令${\displaystyle e}$為權重最小的割邊，假設${\displaystyle T}$為圖的最小生成樹，且${\displaystyle T}$不包含${\displaystyle e}$。那麼如果將${\displaystyle e}$加入${\displaystyle T}$，得到的圖必然含有一條經過${\displaystyle e}$的環，且這個環也含有另一條割邊--設為${\displaystyle e'}$，${\displaystyle e'}$的權重必然大於${\displaystyle e}$，那麼用${\displaystyle e}$替換${\displaystyle e'}$可以形成一個權值小於${\displaystyle T}$的生成樹，與${\displaystyle T}$為最小生成樹矛盾。所以假設不成立，因此${\displaystyle T}$必然包含${\displaystyle e}$。^[2]。

最小權值邊

如果圖的具有最小權值的邊只有一條，那麼這條邊包含在任意一個最小生成樹中。

證明：
假設該邊${\displaystyle e}$沒有在最小生成樹${\displaystyle T}$中，那麼將${\displaystyle e}$加入${\displaystyle T}$中會形成環，用${\displaystyle e}$替換環中的任意一條權值更大的邊，將會形成權值更小的生成樹，與題設矛盾。

相關算法

歷史簡介

計算稠密圖的最小生成樹最早是由羅伯特·C·普里姆在1957年發明的^[3]，即普里姆算法。之後艾茲赫爾·戴克斯特拉也獨自發明了它^[4]。但該算法的基本思想是由沃伊捷赫·亞爾尼克（英語：Vojtěch Jarník）於1930年發明的^[5]。所以該算法有時候也被稱為亞爾尼克算法或者普里姆-亞爾尼克算法。20世紀70年代，優先隊列發明之後很快被用在了尋找稀疏圖中的最小生成樹上。1984年，邁克爾·弗里德曼和羅伯特·塔揚發明了斐波那契堆，普里姆算法所需要的運行時間在理論上由${\displaystyle E\log E}$提升到了${\displaystyle E+V\log V}$。約瑟夫·克魯斯卡爾在1956年發表了他的算法，在他的論文中提到了普里姆算法的一個變種，而奧塔卡爾·布盧瓦卡（英語：Otakar Borůvka）在20世紀20年代的論文中就已經提到了該變種。M.Sollin在1961年重新發現了該算法，該算法後成為實現較好漸進性能的最小生成樹算法和並行最小生成樹算法的基礎^[6]。

以下各算法介紹中，${\displaystyle E}$表示圖的邊數，${\displaystyle V}$表示圖的頂點數。　

布盧瓦卡算法

第一個用於尋找最小生成樹的算法由捷克科學家奧塔卡爾·布盧瓦卡（英語：Otakar Borůvka）提出，即布盧瓦卡算法（英語：Borůvka's algorithm）。

普里姆算法

主條目：普里姆算法

普里姆算法的每一步都會為一棵生長中的樹添加一條邊，該樹最開始只有一個頂點，然後會添加${\displaystyle V-1}$個邊。每次總是添加生長中的樹和樹中除該生長的樹以外的部分形成的切分的具有最小權值的橫切邊。

普里姆算法的時間複雜度為${\displaystyle O(E+V\log V)}$。

克魯斯克爾算法

主條目：克魯斯克爾演算法

按照邊的權重順序（從小到大）將邊加入生成樹中，但是若加入該邊會與生成樹形成環則不加入該邊。直到樹中含有${\displaystyle V-1}$條邊為止。這些邊組成的就是該圖的最小生成樹。

克魯斯克爾算法的時間複雜度為${\displaystyle E\log E}$。

更快的算法

一些研究者希望可以找出更為高效的算法，在這方面也有了一定的成果。 Karger, Klein & Tarjan (1995)針對邊的權值可以成對比較的特殊模型提出了一個基於Borůvka算法和翻轉刪除算法的可以在線性時間內解決最小生成樹的算法^[7][8]。

最快的非隨機比較算法是由伯納德·沙澤勒（英語：Bernard Chazelle）提出的。該算法依賴於soft heap（英語：soft heap）這樣一個類似於優先級隊列的數據結構^[9][10] 。該算法的時間複雜度為${\displaystyle O(E\alpha (E,V))}$。${\displaystyle \alpha }$就是阿克曼函數反函數，${\displaystyle \alpha }$的增長速度非常慢，對於一般的數值來說，其值很難超過5，所以該算法的複雜度可以近似看成是線性時間。

線性時間的最小生成樹算法

目前，既不能證明不存在能在線性時間內得到任意圖的最小生成樹的算法，也未能發明能夠在線性時間內計算稀疏圖的最小生成樹的算法。

相關問題

k-最小生成樹（英語：k-minimum spanning tree）：圖中包含k個頂點的所有子圖的所有最小生成樹中權值最小的生成樹。

歐幾里得最小生成樹（英語：Euclidean minimum spanning tree）是一個用歐幾里得距離來表示權值的連通加權圖的最小生成樹。

方格線最小生成樹（英語：rectilinear minimum spanning tree）是一個用曼哈頓距離來表示權值的連通加權圖的最小生成樹。

容量最小生成樹（英語：capacitated minimum spanning tree）是一棵樹且其每個節點的子樹的容量都不大於${\displaystyle C}$。解決該問題是NP困難的^[11]。但是伊薩·威廉姆斯和夏爾馬以及提出了可以在接近多項式時間內解決該問題的啟發式。

度受限最小生成樹（英語：degree-constrained spanning tree）是一棵樹，其每一個頂點連接的頂點數都不超過d。對一些特定的d值，該問題類似於旅行推銷員問題。該問題也是NP困難的。

對有向圖來說，其與最小生成樹類似的圖處理問題叫做最小樹形圖問題。

最大生成樹是一棵比其它所有生成樹都要大或者相等的生成樹。其解決方法類似於最小生成樹算法。求解最大生成樹的算法在自然語言處理以及條件隨機場這些問題上起到很大的作用^[12]。

動態最小生成樹是在已經計算完一個圖的最小生成樹後動態改變一些邊的取值或刪除/添加一些點或者邊，求解新圖的最小生成樹^[13][14][15]。

注釋

^1 ：用一條邊鏈接樹中的任意兩個頂點都會產生一個新的環。

參考

1. Minimum Spanning Trees. princeton.edu. 2015-09-13 [2016-02-08]. （原始內容存檔於2020-09-27） （英語）.
2. Robert Sedgewick, Kevin Wayne. 算法. 北京: 人民郵電出版社. 2012年10月 [2016-02-03]. ISBN 978-7-115-29380-0.，p391--p392
3. Prim, R. C., Shortest connection networks And some generalizations, Bell System Technical Journal, November 1957, 36 (6): 1389–1401, doi:10.1002/j.1538-7305.1957.tb01515.x.
4. Dijkstra, E. W., A note on two problems in connexion with graphs (PDF), Numerische Mathematik, 1959, 1: 269–271 [2016-02-06], doi:10.1007/BF01386390, （原始內容存檔 (PDF)於2020-01-23）.
5. Jarník, V., O jistém problému minimálním [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 1930, 6: 57–63 [2016-02-06], （原始內容存檔於2017-06-17） （捷克語）.
6. Robert Sedgewick, Kevin Wayne. 算法. 北京: 人民郵電出版社. 2012年10月 [2016-02-03]. ISBN 978-7-115-29380-0.，p407--p408
7. Karger, David R.; Klein, Philip N.; Tarjan, Robert E., A randomized linear-time algorithm to find minimum spanning trees, Journal of the Association for Computing Machinery, 1995, 42 (2): 321–328, MR 1409738, doi:10.1145/201019.201022
8. Pettie, Seth; Ramachandran, Vijaya, Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms, Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02), San Francisco, California: 713–722, 2002.
9. Chazelle, Bernard, A minimum spanning tree algorithm with inverse-Ackermann type complexity, Journal of the Association for Computing Machinery, 2000, 47 (6): 1028–1047, MR 1866456, doi:10.1145/355541.355562.
10. Chazelle, Bernard, The soft heap: an approximate priority queue with optimal error rate, Journal of the Association for Computing Machinery, 2000, 47 (6): 1012–1027, MR 1866455, doi:10.1145/355541.355554.
11. Jothi, Raja; Raghavachari, Balaji, Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design, ACM Trans. Algorithms, 2005, 1 (2): 265–282, doi:10.1145/1103963.1103967
12. McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, Jan. Non-projective dependency parsing using spanning tree algorithms (PDF). Proc. HLT/EMNLP. 2005 [2016-02-06]. （原始內容存檔 (PDF)於2020-10-01）.
13. Spira, P. M.; Pan, A., On finding and updating spanning trees and shortest paths, SIAM Journal on Computing, 1975, 4 (3): 375–380, MR 0378466, doi:10.1137/0204032.
14. Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel, Poly-logarithmic deterministic fully dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the Association for Computing Machinery, 2001, 48 (4): 723–760, MR 2144928, doi:10.1145/502090.502095.
15. Chin, F.; Houck, D., Algorithms for updating minimal spanning trees, Journal of Computer and System Sciences, 1978, 16 (3): 333–344, doi:10.1016/0022-0000(78)90022-3.

參考文獻

• Otakar Boruvka on Minimum Spanning Tree Problem (translation of the both 1926 papers, comments, history) (2000) （頁面存檔備份，存於網際網路檔案館） Jaroslav Nešetřil, Eva Milková, Helena Nesetrilová. (Section 7 gives his algorithm, which looks like a cross between Prim's and Kruskal's.)
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 23: Minimum Spanning Trees, pp. 561–579.
• Eisner, Jason (1997). State-of-the-art algorithms for minimum spanning trees: A tutorial discussion （頁面存檔備份，存於網際網路檔案館）. Manuscript, University of Pennsylvania, April. 78 pp.
• Kromkowski, John David. "Still Unmelted after All These Years", in Annual Editions, Race and Ethnic Relations, 17/e (2009 McGraw Hill) (Using minimum spanning tree as method of demographic analysis of ethnic diversity across the United States).

外部連結

• Implemented in BGL, the Boost Graph Library （頁面存檔備份，存於網際網路檔案館）
• The Stony Brook Algorithm Repository - Minimum Spanning Tree codes （頁面存檔備份，存於網際網路檔案館）
• Implemented in QuickGraph for .Net