最小生成树

由生成树的定义可知，无向连通图的生成树不是唯一的。连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。

可以证明，对于有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1条边。

下面介绍两种常见的构造最小生成树的算法：普里姆算法和克鲁斯卡尔算法。

（1）普里姆（Prim）算法

普里姆算法的基本思想是：取图中任意一个顶点 v 作为生成树的根，寻找生成树之外的某个w顶点，往生成树上添加这个顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中权值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。

（2）克鲁斯卡尔（Kruskal）算法

克鲁斯卡尔算法的基本思想是：为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。

具体做法是：先构造一个只含 n 个顶点没有边的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。