1.最小生成树：
无向连通图的所有生成树中有一棵边的权值总和最小的生成树
1.1 问题背景：
假设要在n
个城市之间建立通信联络网，则连通n
个城市只需要n—1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。在每两个城市之间都可以设立一条线路，相应地都要付出一定的经济代价。n
个城市之间，最多也许设立n(n-1)/2条线路，那么，如何在这些也许的线路中选择n-1条，以使总的花费最少呢?
1.2 分析问题（建立模型）：
可以用连通网来表达n
个城市以及n
个城市间也许设立的通信线路，其中网的顶点表达城市，
边表达两城市之间的线路，
赋于边的权值表达相应的代价。对于n
个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。即无向连通图的生成树不是唯一的。连通图的一次遍历所通过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就也许得到不同的生成树。
图 G5无向连通图的生成树 为(a)、(b)和(c)图所示：
G5G5的三棵生成树
：可以证明，对于有n
个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅 ...