最小生成树

最小生成树是一副连通加权无向图中一棵权值最小的生成树。

一个平面图和它的最小生成树。在该图中，边的长度正比于权值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}$ 的一部分。

在一幅连通加权无向图中，给定任意的切分（英语：Cut (graph theory)），如有一条横切边的权值严格小于所有其他横切边，则这条边必然属于图的最小生成树。

证明：
令${\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}$ 为最小生成树矛盾。所以假设不成立^[2]。

最小权值边

如果图的具有最小权值的边只有一条，那么这条边包含在任意一个最小生成树中。

证明：
假设该边${\displaystyle e}$ 没有在最小生成树${\displaystyle T}$ 中，那么将${\displaystyle e}$ 加入${\displaystyle T}$ 中会形成环，用${\displaystyle e}$ 替换环中的任意一条权值更大的边，将会形成权值更小的生成树，与题设矛盾。

相关算法

历史简介

计算稠密图的最小生成树最早是由罗伯特·普里姆（英语：Robert C. Prim）在1957年发明的^[3]，即Prim算法。之后艾兹赫尔·戴克斯特拉也独自发明了它^[4]。但该算法的基本思想是由沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）于1930年发明的^[5]。所以该算法有时候也被称为Jarník算法或者Prim-Jarník算法。20世纪70年代，优先队列发明之后很快被用在了寻找稀疏图中的最小生成树上。1984年，迈克尔·弗里德曼和罗伯特·塔扬发明了斐波那契堆，Prim算法所需要的运行时间在理论上由${\displaystyle E\log E}$ 提升到了${\displaystyle E+V\log V}$ 。约瑟夫·克鲁斯卡尔（英语：Joseph Kruskal）在1956年发表了他的算法，在他的论文中提到了Prim算法的一个变种，而奥塔卡尔·布卢瓦卡（英语：Otakar Borůvka）在20世纪20年代的论文中就已经提到了该变种。M.Sollin在1961年重新发现了该算法，该算法后成为实现较好渐进性能的最小生成树算法和并行最小生成树算法的基础^[6]。

以下各算法介绍中，${\displaystyle E}$ 表示图的边数，${\displaystyle V}$ 表示图的顶点数。　

Borůvka算法

第一个用于寻找最小生成树的算法由捷克科学家奥塔卡尔·布卢瓦卡（英语：Otakar Borůvka）提出，即Borůvka算法（英语：Borůvka's algorithm）。

Prim算法

主条目：普里姆算法

Prim算法的每一步都会为一棵生长中的树添加一条边，该树最开始只有一个顶点，然后会添加${\displaystyle V-1}$ 个边。每次总是添加生长中的树和树中除该生长的树以外的部分形成的切分的具有最小权值的横切边。

Prim算法的时间复杂度为${\displaystyle O(E+V\log V)}$ 。

Kruskal算法

主条目：克鲁斯克尔演算法

按照边的权重顺序（从小到大）将边加入生成树中，但是若加入该边会与生成树形成环则不加入该边。直到树中含有${\displaystyle V-1}$ 条边为止。这些边组成的就是该图的最小生成树。

Kruskal算法的时间复杂度为${\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月. ISBN 978-7-115-29380-0.  使用|accessdate=需要含有|url= (帮助)，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月. ISBN 978-7-115-29380-0.  使用|accessdate=需要含有|url= (帮助)，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 （页面存档备份，存于互联网档案馆）