最小生成树

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

在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即 ${\displaystyle (u,v)\in <!--\; \in \; -->E}$），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即 ${\displaystyle T\subseteq <!--\; \subseteq \; -->E}$）且 (V, T) 为树，使得

的 w(T) 最小，则此 T 为 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}$是最小生成树矛盾。

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

证明：
令${\displaystyle e}$为权重最小的横切边，假设${\displaystyle T}$为图的最小生成树，且${\displaystyle T}$不包含${\displaystyle e}$。那么如果将${\displaystyle e}$加入${\displaystyle T}$，得到的图必然含有一条经过${\displaystyle e}$的环，且这个环也含有另一条横切边--设为${\displaystyle e^{\prime }}$，${\displaystyle e^{\prime }}$的权重必然大于${\displaystyle e}$，那么用${\displaystyle e}$替换${\displaystyle e^{\prime }}$可以形成一个权值小于${\displaystyle T}$的生成树，与${\displaystyle T}$为最小生成树矛盾。所以假设不成立。

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

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

计算稠密图的最小生成树最早是由罗伯特·普里姆（英语：Robert C. Prim）在1957年发明的，即Prim算法。之后艾兹赫尔·戴克斯特拉也独自发明了它。但该算法的基本思想是由沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）于1930年发明的。所以该算法有时候也被称为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年重新发现了该算法，该算法后成为实现较好渐进性能的最小生成树算法和并行最小生成树算法的基础。

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

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

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

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

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

Kruskal算法的时间复杂度为${\displaystyle E\log <!--\; \; -->E}$。

一些研究者希望可以找出更为高效的算法，在这方面也有了一定的成果。Karger，Klein & Tarjan (1995)针对边的权值可以成对比较的特殊模型提出了一个基于Borůvka算法和翻转删除算法的可以在线性时间内解决最小生成树的算法。

最快的非随机比较算法是由伯纳德·沙泽勒（英语：Bernard Chazelle）提出的。该算法依赖于soft heap（英语：soft heap）这样一个类似于优先级队列的数据结构 。该算法的时间复杂度为${\displaystyle O(E\mathrm{\alpha <!--\; \alpha \; -->}(E,V))}$。${\displaystyle \mathrm{\alpha <!--\; \alpha \; -->}}$就是阿克曼函数反函数，${\displaystyle \mathrm{\alpha <!--\; \alpha \; -->}}$的增长速度非常慢，对于一般的数值来说，其值很难超过5，所以该算法的复杂度可以近似看成是线性时间。

目前，既不能证明不存在能在线性时间内得到任意图的最小生成树的算法，也未能发明能够在线性时间内计算稀疏图的最小生成树的算法。

k-最小生成树（英语：k-minimum spanning tree）：图中包含k个顶点的所有子图的所有最小生成树中权值最小的生成树。

欧几里得最小生成树（英语：Euclidean minimum spanning tree）是一个用欧几里得距离来表示权值的连通加权图的最小生成树。

方格线最小生成树（英语：rectilinear minimum spanning tree）是一个用曼哈顿距离来表示权值的连通加权图的最小生成树。

容量最小生成树（英语：capacitated minimum spanning tree）是一棵树且其每个节点的子树的容量都不大于${\displaystyle C}$。解决该问题是NP困难的。但是伊萨·威廉姆斯和夏尔马以及提出了可以在接近多项式时间内解决该问题的启发式。

度受限最小生成树（英语：degree-constrained spanning tree）是一棵树，其每一个顶点连接的顶点数都不超过d。对一些特定的d值，该问题类似于旅行推销员问题。该问题也是NP困难的。

对有向图来说，其与最小生成树类似的图处理问题叫做最小树形图问题。

最大生成树是一棵比其它所有生成树都要大或者相等的生成树。其解决方法类似于最小生成树算法。求解最大生成树的算法在自然语言处理以及条件随机场这些问题上起到很大的作用。

动态最小生成树是在已经计算完一个图的最小生成树后动态改变一些边的取值或删除/添加一些点或者边，求解新图的最小生成树。

^1 ：用一条边链接树中的任意两个顶点都会产生一个新的环。

^2 ：设最小生成树${\displaystyle A}$的边的权值集合按从小到大顺序排列为${\displaystyle \left\{e_1,e_2,e_3,\cdots <!--\; \cdots \; -->,e_n\right\}}$，${\displaystyle B}$的为${\displaystyle \left\{f_1,f_2,f_3,\cdots <!--\; \cdots \; -->,f_n\right\}}$。因为${\displaystyle e_k}$为在${\displaystyle A}$但是不在${\displaystyle B}$的边中权值最小的边，所以${\displaystyle A}$中权值小于${\displaystyle e_k}$的边也在${\displaystyle B}$中。所以子图${\displaystyle A1}$${\displaystyle \left\{e_1,e_2,e_3,\cdots <!--\; \cdots \; -->,e_{k-<!--\; -\; -->1},e_k\right\}}$==${\displaystyle B1}$${\displaystyle \left\{f_1,f_2,f_3,\cdots <!--\; \cdots \; -->,f_{k-<!--\; -\; -->1},f_k\right\}}$。因为${\displaystyle A1}$没有环，所以${\displaystyle B1}$且${\displaystyle B1}$的子图都没有环，那么组成环${\displaystyle C}$的边中必有边来自${\displaystyle \left\{f_{k+1},f_{k+2},f_{k+3},\cdots <!--\; \cdots \; -->,f_i\right\}(i>k)}$之中。