最小生成树 -{H|zh-hans:重定向;zh-hant:重新导向;}--{H|zh-cn:字符;zh-tw:字元;}--{H|zh-hans:文件; zh-hant:档案;}--{H|zh-hans:快捷方式; zh-hant:捷径;}--{H|zh-hans:项目;zh-hant:专案;zh-tw:计划;zh-hk:计划;zh-mo:计划;}--{H|zh-cn:计算机; zh-sg:电脑; zh-tw:电脑;}- 最小生成树（，简称MST）是最小权重生成树（）的简称，是一副连通加权无向图中一棵权值最小的生成树。 在一给定的无向图 formula_1 中，formula_2 代表连接顶点 u 与顶点 v 的边（即 formula_3），而 formula_4 代表此边的权重，若存在 T 为 E 的子集（即 formula_5）且 (V, T) 为树，使得： formula_6 的 w(T) 最小，则此 T 为 G 的最小生成树。 一个连通图可能有多个生成树。当图中的边具有权值时，总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言，对于非连通无向图来说，它的每一连通分量同样有最小生成树，它们的并被称为最小生成森林。 以有线电视电缆的架设为例，若只能沿著街道布线，则以街道为边，而路口为顶点，其中必然有一最小生成树能使布线成本最低。 相关性质. 存在个数. 最小生成树在一些情况下可能会有多个。例如，当图的每一条边的权值都相同时，该图的所有生成树都是最小生成树。 唯一性. 如果图的每一条边的权值都互不相同，那么最小生成树将只有一个。这一定理同样适用于最小生成森林。 证明： 假设图formula_7为每条边权值互不相同的连通图，且有两个不同的最小生成树formula_8和formula_9。 则formula_8中必然存在一些在formula_9中并不存在的边，取其中一条这样的边formula_12。 因为formula_9是最小生成树，所以若往formula_9中添加边formula_12，则将会出现环路。（因为有formula_16个顶点的树有且仅有formula_17条边） 同时可知，如果从formula_8中删除边formula_12，则formula_8将分为互不连通的两个连通分量。因为formula_21，所以formula_9中必然有其他的边连接这两个连通分量。且将formula_12加入formula_9后形成的环路中，除了formula_12外至少有另一条连接formula_8中删除formula_12后的这两个连通分量的边。取其中一条这样的边，记作formula_28。此时若将formula_28加入formula_8，则可连接从formula_8中删除formula_12后得到的两个连通分量，并形成一棵不同的生成树。 因为formula_7中所有边的权值互不相同，所以关于formula_12和formula_28的权重大小关系，可能有以下两种情况之一： 综上，若formula_7各边权重互不相等，则不可能存在两棵互不相同的最小生成树。即formula_7的最小生成树是唯一的。 边的权值之和最低的子图. 如果图的边的权值都为正数，那么最小生成树就是该图的所有包含所有顶点的子图中权值最低的连通子图。 环定理. 对于连通图中的任意一个环formula_48：如果formula_48中有边formula_50的权值大于该环中任意一个其它的边的权值，那么这个边不会是最小生成树中的边 证明： 假设formula_50属于最小生成树formula_52，那么将formula_50删去将会使得formula_52变为两个树。因为环formula_48必然还存在另一横切边ｆ可以连接两个子树形成生成树formula_56，且由于formula_57＜formula_50，生成树formula_56权值更小，与formula_52是最小生成树矛盾。 割定理. 在一幅连通加权无向图中，给定任意的割，如有一条割边的权值严格小于所有其他割边，则这条边必然属于图的最小生成树。 证明： 令formula_50为权重最小的割边，假设formula_8为图的最小生成树，且formula_8不包含formula_50。那么如果将formula_50加入formula_8，得到的图必然含有一条经过formula_50的环，且这个环也含有另一条割边--设为formula_68，formula_68的权重必然大于formula_50，那么用formula_50替换formula_68可以形成一个权值小于formula_8的生成树，与formula_8为最小生成树矛盾。所以假设不成立，因此formula_8必然包含formula_50。。 最小权值边. 如果图的具有最小权值的边只有一条，那么这条边包含在任意一个最小生成树中。 证明： 假设该边formula_50没有在最小生成树formula_8中，那么将formula_50加入formula_8中会形成环，用formula_50替换环中的任意一条权值更大的边，将会形成权值更小的生成树，与题设矛盾。 相关算法. 历史简介. 计算稠密图的最小生成树最早是由罗伯特·C·普里姆在1957年发明的，即普里姆算法。之后艾兹赫尔·戴克斯特拉也独自发明了它。但该算法的基本思想是由于1930年发明的。所以该算法有时候也被称为亚尔尼克算法或者普里姆-亚尔尼克算法。20世纪70年代，优先队列发明之后很快被用在了寻找稀疏图中的最小生成树上。1984年，迈克尔·弗里德曼和罗伯特·塔扬发明了斐波那契堆，普里姆算法所需要的运行时间在理论上由formula_82提升到了formula_83。约瑟夫·克鲁斯卡尔在1956年发表了他的算法，在他的论文中提到了普里姆算法的一个变种，而在20世纪20年代的论文中就已经提到了该变种。M.Sollin在1961年重新发现了该算法，该算法后成为实现较好渐进性能的最小生成树算法和并行最小生成树算法的基础。 以下各算法介绍中，formula_84表示图的边数，formula_85表示图的顶点数。　 布卢瓦卡算法. 第一个用于寻找最小生成树的算法由捷克科学家提出，即。 普里姆算法. 普里姆算法的每一步都会为一棵生长中的树添加一条边，该树最开始只有一个顶点，然后会添加formula_86个边。每次总是添加生长中的树和树中除该生长的树以外的部分形成的切分的具有最小权值的横切边。 普里姆算法的时间复杂度为formula_87。 克鲁斯克尔算法. 按照边的权重顺序（从小到大）将边加入生成树中，但是若加入该边会与生成树形成环则不加入该边。直到树中含有formula_88条边为止。这些边组成的就是该图的最小生成树。 克鲁斯克尔算法的时间复杂度为formula_82。 更快的算法. 一些研究者希望可以找出更为高效的算法，在这方面也有了一定的成果。 最快的非随机比较算法是由提出的。该算法依赖于这样一个类似于优先级队列的数据结构 。该算法的时间复杂度为formula_90。formula_91就是阿克曼函数反函数，formula_91的增长速度非常慢，对于一般的数值来说，其值很难超过5，所以该算法的复杂度可以近似看成是线性时间。 线性时间的最小生成树算法. 目前，既不能证明不存在能在线性时间内得到任意图的最小生成树的算法，也未能发明能够在线性时间内计算稀疏图的最小生成树的算法。 相关问题. ：图中包含k个顶点的所有子图的所有最小生成树中权值最小的生成树。 是一个用欧几里得距离来表示权值的连通加权图的最小生成树。 是一个用曼哈顿距离来表示权值的连通加权图的最小生成树。 是一棵树且其每个节点的子树的容量都不大于formula_48。解决该问题是NP困难的。但是伊萨·威廉姆斯和夏尔马以及提出了可以在接近多项式时间内解决该问题的启发式。 是一棵树，其每一个顶点连接的顶点数都不超过d。对一些特定的d值，该问题类似于旅行推销员问题。该问题也是NP困难的。 对有向图来说，其与最小生成树类似的图处理问题叫做最小树形图问题。 最大生成树是一棵比其它所有生成树都要大或者相等的生成树。其解决方法类似于最小生成树算法。求解最大生成树的算法在自然语言处理以及条件随机场这些问题上起到很大的作用。 动态最小生成树是在已经计算完一个图的最小生成树后动态改变一些边的取值或删除/添加一些点或者边，求解新图的最小生成树。 注释. ^1 ：用一条边链接树中的任意两个顶点都会产生一个新的环。