- 1 - 一、题目描述： 如图所示的赋权图表示某七个城市及预算它们之间的一些某些直接通信道路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小并计算其最小值。 二、题目分析： 该题即要求赋权图的最小生成树，即可使得各城市间互相通信又使造价费用最小。 1 .生成树及最小生成树定义 (1)生成树的定义入下： 对于有 n 个顶点的无向连通图 G，把遍历过程中顺序访问的两个顶点之间的路径记录下来，这样 G 中的 n 个顶点以及由出发点一次访问其余 n-1 个顶点所经过的 n-1 条边就构成了G 的极小连通子图，也就是 G 的一棵生成树，出发顶点是生成树的根。 (2)下面给出最小生成树的概念： 给定一个连通网络，要求构造具有最小代价的生成树时，也即使生成树的各边的权值总和达到最小。把生成树各边的权值总和定义为生成树的权，那么具有最小权值的生成树就构成了连通网络的最小生成树。 2 .最小生成树的性质 构造最小生成树的算法有很多种，其中大多数的算法都利用了最小生成树的一个性质，简称为 MST 性质：假设 G=（V，E）是一个连通网络，U 是 V 中的一个真子集，若存在顶点Uu 和顶点)(UVv的边(u，v)是一条具有最小权值的边，则必存在 G 的一棵最小生成树包括这条边(u，v)。 3 .常用算法及思想 利用该性质构造最小生成树的常用算法主要有：Prim(普里姆)算法和 Kruskal(克鲁斯卡尔)算法。 (1)Prim 算法思想： 设 G=（V,E）是一个有 n 个顶点的连通图，用 T=(U，TE)表示要构造的最小生成树，其中 U 为顶点集合，TE 为边的集合。则 Prim 算法的具体步骤描述入下： 初始化：令 U={Ø }，TE={Ø }。从 V 中取出一个顶点0u 放入生成树的顶点集 U 中，作为 - 2 - 第一个顶点，此时}){},({0uT ； 从Uu ，)(UVv的边(u，v)中找一条代价最小的边),(** vu，将其放入TE 中，并将*v 放入U 中； 重复步骤（2），直至U=V 为止。此时集合TE 中必有n-1 条边，T 即为所要构造的最小生成树。 (2)Kruskal 算法思想： 设G=（V,E）是一个有n 个顶点的连通图，则令最小生成树的初始状态为只有n 个顶点而无任何边的非连通图T={V,{Ø }},图中每个顶点自成一个连通分量。依次选择E 中的最小代价边，若该边依附于T 中的两个不同的连通分量，则将此边加入到T 中；否则，舍去此边而选择下一条代价最小的边。以此类推，直到T 中所有...
