最小生成树的两种算法及证明

首先，什么是平面连通图?

平面连通图是一个二维网络,网络由节点和边组成,比如我随手画了一个:

也可以是这样:

它并不是一个空间连通图因为他可以拓扑变换成这样:

但如果这种图就不行了:

这样的连通图只能出现在三维空间中,所以无法满足欧拉公式.

其次，欧拉公式是沃特?

欧拉公式也叫欧拉定理,指在简单多面体上，棱数（边）、面数和点数具有一定的关系：点+面=边+2。而且规定,平面网络属于特殊的一种多面体,想不到吧（关于欧拉定理的详解，请转向我的另一篇论文《浅谈欧拉定理》），这里要注意一下，数面数的时候要算上整个图外侧的那个无穷大的面，也就是环路的数量加上1。因此平面连通图恒满足欧拉定理。

至于我为什么要介绍欧拉公式呢，是为了做准备，后面的最小生成树需要用到它！

然后，生成树有啥特点？

在平面连通图中，我们想要用一个如树枝一般层层分岔但无环的线路经过所有的节点，且这个线路必须被包含于连通图。换个说法就是，在这个连通图中，我们希望删除掉一些边，让剩下所有的边都没有形成环，且剩下的边必须相互连通，不能被隔绝，这就是生成树（spanning tree）。比如这样：

可以看出，不同的删边方法可以得到不同的生成树。

根据欧拉公式，生成树中的面数为1，点数不变还是n，因而得到边数等于n-1，对于连通图中的所有生成树都成立。

还是根据欧拉公式可以证明，此时在生成树中随便增添一条边（这条边当然要属于原连通图中），都必然将多出一个环，增加n条边就产生n个环。

把这张连通图看成一张地图，每个节点都是一个地点，每条边都是可走的路径，这时给每条路径赋予一个权重值，代表这条路径的长短，这在TCP/IP协议中叫做度量值或开销（cost），所以这里权值越大，路径开销反而越大。

因此，不同的生成树的总开销未必相同，其中总开销最小的就成为了本文探讨的最小生成树。

还可以看出，在树上，任意两点之间走的路径是最短距离（放之于原来的连通图比较来说）的可能性很小。所以最小生成树不是地图上寻路的最好方法。

之后，求最小生成树的两种重要算法

以上都是最基础的铺垫部分，写教程就这点麻烦，一定要从知识的根源开始讲起。那么废话不再多说，直接上算法：kruskal（克鲁斯卡尔）算法和prim（普利木）算法。这两个算法是计算最小生成树最常用的算法没有之一，因为他们既简单又完美，况且他们有很多的相似之处。

~~Kruskal Algorithm~~

前期准备：

记平面连通图为G（Graph），设有n个节点，x条边。给所有的边编号并按照权重从小到大排序（有并列相等的顺序随便）放入集合A中，设一个容量为n-1的集合B用来存放最小生成树的所有边，设一个容量为x-n+1的集合C用来存放G中被删除掉的边。

kruskal算法是由一个个递进的循环周期组成的，每个循环周期的步骤如下：

先从A中取出权重最小（权重相等选编号更小的）的边放入B中，同时要保证这条边不能和B中已有的边在G中构成环路，如果它是会构成环路的边，它将进入C，然后选择剩下最小权重的边。以此循环直到A中的边全部被取走。做成流程图就是酱紫的：

然后给一个过程图，大家自己意会：

怎么样简单粗暴吧，虽然算法看上去简单的感人，但是该如何证明它的正确性呢？

我们需要证明两点，第一：kruskal算出来的是生成树；第二：它是最小生成树。

证明它是个生成树：

根据之前对生成树下的定义，首先要覆盖所有点，其次不能有环，最后不能有断路。

第一点：很容易，既然通过集合A、B、C包含所有边的洗牌过程，自然照顾到了G中所有的点。

第二点：更容易，每个循环中都要检查一遍是否与之前的”小树苗“形成环路，最后肯定无环。

第三点：可以用反证法，假设最后生成了相互隔离的两棵树，因为总共循环了x次（每条边各一次），两棵树中间的那些边（C中可以连接两棵树的边）当初被审查的时候肯定会被纳入B，与“纳入C”矛盾，所以不可能生成两棵树。

证明它是最小生成树：

这个地方考验大家的空间想象能力，如果想不出来可以画图。

同样是反证法：

对于一个连通图G,假如通过kruskal算法得到的生成树(记为K)不是最小生成树(记为T),那么由欧拉公式可知,”正真的”最小生成树T和通过kruskal算法得到的生成K树拥有相同的边数.那么设K中有y条边是T中没有的,反之T中也有y条边是K中没有的.无论是K还是T,在其中任意添加一条新边(属于G),都将产生一个环.

现在开始做一系列的变换,将K变换成T:

选择T中K没有的一条边(记为L1)加入到K中,此时K中必然产生一个环！！,从这个环中选择另一条边(记为L2),删除之而打破这个环,而且L2必须是T中没有的(肯定存在这一条边因为T中的那一处无环！！！).以此类推,经过y次变换后K变成了总权重值更小的T.

那么在上述过程中,肯定有一对L1L2中L1<L2,那么当初kruskal选路过程中，当选到L2的时候,意味着L2不会形成环切权最小,而此时L1也不会形成环,所以此时应该选择L1，与“选择L2”矛盾,得以证明假设不成立，所以kruskal算出来的是最小生成树。完。

~~Prim Algorithm~~

prim算法和经典的Dijkstra最短路径寻路算法惊人的相似，都是采用层层扩散的方式收敛出树。同时又与kruskal算法分享着类似的逻辑。关于Dijkstra算法敬请参考之前发布的《SPF算法完美教程》，如果没听过它也无碍，prim算法将展示它的思想。

前提准备：总共n个节点编号，放入集合甲中，设一个集合乙用来存放生成树成长过程中依次覆盖的节点，记这棵生成树年轻时为T。（注意，这是个动态生长的树，从0开始直到长成最小生成树）

Prim算法的基本流程（一个周期）：（同kruskal一样也是通过一个个简单的循环来完成的）

首先,从甲中取出一个距离T最短的节点Q，就是乙中所有节点的所有外部邻居中最近的那个点，如果是第一次循环的话就从甲中随机取出一点。（若是并列最短就随便选）。然后将这个点加入到乙中。以此循环直到甲空掉了为止。

(*@ο@*) 哇～是不是感觉比kruskal算法还要简单直接，流程图都不需要画了（因为是一条笔直的直线流程），如果将各个循环结束时的状态图记录下来，就会看到一棵生成树从小长到大的过程。如同这个动态图：

有待调用的重要前提：

在证明prim算法之前我们需要用到一个底层结论：在一个连通图G中，对于每个点，与自己相连的最短边一定属于G的生成树。（如果有并列则任意一个最短边）

这个结论very重要，想要证明他也很easy，还是用万能的反证法：

对于一个点Q它连接着m条边，其中有一条最短边L，G的最小生成树T不经过L，那么对于Q剩下m-1条边中至少有一条边连接Q与T，设有z条这样的边（0<z<m）。

那么如果此时在T中把Q及Q连接的m条边都移除，T剩下的部分将被分成z个相互隔离的部分（生成树的特性），而且Q关于L对称的那个点有且只有属于z个部分中的某一个部分。那么问题来了，属于的那个部分与Q相连的边应当被替换成开销更小的L，所以与T是最小生成树矛盾，得以反证。

上图解（图中z=3）：

这样就一清二楚了（吧？），图中各个区域的“树枝”符号就代表了被分割的部分树，他们之间只能通过Q相通。所以Q的最短边L必然在真正的生成树中。

数学归纳法证明：

有了这个结论后大势已定，接下来我将展示用经典的数学归纳法证明prim算法，其中以集合乙中的节点数量为递增变量（所以这里的n是动态的），也可以看成是动态增长的树T。

n=1，选择任意一个点Q1。

n=2，Q1发散到最近的Q2其中边L1属于最终最小生成树T，成立。

假设n=k的时候成立，也就是Q1Q2Q3一直到Qk所在的T属于最终最小生成树。

那么接下来做一个惊人之举：把此时的T整体看成一个节点。为什么可以这么看呢，因为T和一个节点share共同的属性：都是属于最终生成树；都有若干个与自己相连的边。因而此举不影响最后的生成树。记住，最小生成树的根本目的和原则就是想方设法不择手段地用最少的边连接最多的节点！

当n=k+1的时候，从甲中剩下的节点中选择距离T（点）最近的一条边Lk加入到乙中，根据之前定理，T+Lk一起也属于最终生成树。成立。

由数学归纳法得证prim算法的正确性。完。

最后，两种算法的异同

不难看出，两种基本算法的内容都通俗易懂，只是证明起来略有困难。两者的区别在于，kruskal基于边来收敛，而prim基于点。但是综合来看prim要比kruskal高级一点，在边数比较稠密的情况下用prim求生成树要快于kruskal，因为kruskal是一条边一条边来找的，毕竟prim使用和Dijkstra相似的“堆栈”思想而kruskal是一种贪心算法，当边稀疏时两者都可适用。Anyway，二者都是图论学中非常重要的算法，大家务必牢记！