概述
最小生成树（minimum spanning tree）是图计算中基本的问题，背后的问题非常直接，假设无向连通图G(V, E)，且E中的每条边e有权值（可以表示距离、价值等），找出一颗树，连接G中所有的边，且连接这棵树的所有边的权值之和最小。在电子制造中，如何以最低的成本连接多个针管便是这一问题。
相关概念及算法
下面以一个图来对此进行说明：
图1中灰色的线是最小生成树中的边。图中有9个节点，连接此9个节点的最小生成树有8条边，问题是：如何选择这8条边？
前面两课中介绍了动态规划和贪心算法，都是用来解决最值问题，本文中的最小生成树很显然也属于此类。最小生成树使用贪心算法，文中会对贪心算法的使用进行说明。
假设mst是最终要求的最小生成树，若A是最小生成树mst边集的子集，如果每次选择一条边(u, v)加入A，并且确保A始终是mst边集的子集，则最终得到的A必然是mst最小生成树的边集。这样的边(u, v)称为A的安全边。安全边即为可以选择的边。
为了得到安全边，下面介绍一些概念。无向图G=(V,E)的一个切割(S, V-S)是节点集V的一个划分，如图2所示：
显然，一个切割将图划分为两部分。如果一条边(u,v)，u在S中，v在S-V中，则称边(u,v)横跨切割(S, V-S)。如果集合A中不存在横跨该切割的边，则称该切割尊重A；在横跨切割的所有边中，权重最小的边称为轻量级边（注：轻量级边可能不是唯一的）。
分析：理解上面的定义，假如切割(S, V-S)尊重A，即A中不存在连接切割(S, V-S)的边，要使A最终成长为mst的边集，则必然要求加一条横跨切割(S, V-S)的边，显然，轻量级边就是目标选择！！！
下面的定理和推论保证了Kruskal和Prim算法的正确性，感兴趣的童鞋可以自己证明或参考算法导论中的说明。
定理1: 设G=(V,E)是一个在边E上定义了实数值权重函数w的连通无向图，设A为E的一个子集，且A包括在图G的mst中，设(S, V-S)是图中尊重A的任意一个切割，(u, v)是横跨切割(S, V-S)的一条轻量级边，那么边(u,v)对于集合A是安全的。
推论1: 设G=(V,E)是一个在边E上定义了实数值权重函数w的连通无向图，设A为E的一个子集，且A包括在图G的mst中，设C=(Vc, Ec)为森林GA=(V, A)中的一个连通分量（树）。如果(u,v)是连接C和GA中某个其它连通分量的一条轻量级边，则(u, v)对于集合A是安全的。
根据定理1和推论1，构造最小生成树可以有两种方式，一种是切割的角度，一种是森林的角度。切割的角度：先从图中选取一个点n1，划一个切割({n1}, V-{n1})，然后找这个切割的轻量级边以及这个边在 V-{n1}的节点n2；然后再划一个切割（{n1, n2}, V-{n1, n2})，再找出对应的轻量级边，...,直到所有的节点，每一步中找到的轻量级边组成的集合为最小生成树中的边。
森林的方式是：首先将每个节点都看成一个连通分量（此时有n个连通分量），寻找连通连接连通分量权值最小的边(u, v)，(u, v)连接的连通分量为C1和C2，则(u, v)连接后，合成一个更大的连通分量C12（此时有n-1个连通分量）；然后对n-1个连通分量继续实施上述类似的动作，直至最后变成一个连通分量。
切割的角度对应的是Prim算法，森林的方式对应的是Kruskal算法，算法本身都很简单，在此不再赘述，下面两组从算法导论中摘取的图很好地解释了对应的算法。
小结
最小生成树是图计算中的基本算法，理解算法的关键是切割基础上的轻量级边，上文的说明中野间接解释了利用贪心算法的正确性，相对而言，最小生成树是较为简单和基础的算法，是其他算法的基础。
