算法设计与分析 课件 第五章 贪心法 5.2.2 村村通最小成本问题

计算机算法设计与分析第5章贪心法5.2.2村村通最小成本问题村村通工程（通电、通水、通气、通网、通路等）是中国政府推行的一个旨在改善农村地区基础设施和信息化水平的工程项目。现某乡镇政府决定实现村村通公路，通过勘察已将各个村落之间的可修建道路成本数据统计在下表中，根据表中给出的数据，求使得每个村都有公路连通所需要的最低成本和具体修建线路。村落1111122345村落2345636456成本29845694635.2.2村村通最小成本问题用无向连通带权图G=（V，E）表示村落之间的道路数据及其公路修建成本，如图所示，各个村落为图G的顶点，村落之间有路连通用无向边相连，边的权值为修建村落公路的成本。村村通公路最小成本问题转化为求图G的最小生成树问题。5.2.2村村通最小成本问题对一个无向连通带权图G，如果G的子图G'是一棵包含G的所有顶点的树，则称G'为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。贪心策略1，Prim算法设图G=（V,E）是无向连通带权图，V={1,2,...,n}

，E为边集，cost[i][j]记录顶点i到顶点j这条边的权值。Prim算法构造最小生成树的基本步骤如下：（1）置顶点集合S={1}；（2）只要S中顶点数目小于n，就作如下的贪心选择：选取满足条件i∈S，j∈V-S，且（i,j）边权值cost[i][j]最小，将顶点j添加到S中。这个过程一直进行到|S|=|V|时为止，选取到的所有边恰好构成G的一棵最小生成树。贪心策略1，Prim算法1SSSSSSPrim算法正确性证明对于k<n，存在一棵最小生成树包含Prim算法前k步选择的边。（1）首先证明k=1，存在一棵最小生成树T包含边e=（1，i），其中cost[1][i]是所有关联顶点1的边中权值最小的。Prim算法正确性证明设T是一棵最小生成树，且T不包含边（1，i），则T+（1，i）含有一条回路，删除回路中关联顶点1的另一条边（1，j）得到一棵生成树T'，如图所示。因cost[1][i]≤cost[1][j]，所以生成树T'的权值≤最小生成树T的权值，与T是一棵最小生成树矛盾。因此，与顶点1关联的最小权值边一定包含在一棵生成树中。1ij

T1ij

1ij

T'Prim算法正确性证明（2）假设Prim算法第k步选择的边构成一棵最小生成树的边，证明算法第k+1步选择的边也构成一棵最小生成树的边。假设算法进行了k步，生成树的边为e1,e2,...,ek，这些边的端点构成集合S，由归纳假设存在G的一棵最小生成树T包含这些边。算法第k+1步选择顶点ik+1，则ik+1到S中顶点边权值最小，设此边ek+1=（ik，ik+1）。若ek+1∈T，则算法k+1显然正确。Prim算法正确性证明若T不包含ek+1，将ek+1加T中形成一条回路，这条回路有另外一条连接S与顶点ik+1的边e，令,则T*是一棵生成树，包含e1,e2,...,ek，ek+1，且T*的各边权值之和小于等于T的各边权值之和，说明T*也是一颗最小生成树，算法到k+1步仍然得到最小生成树。证明过程如图所示。权值最小ek+1i1ikS1

V-Sik+1e时间效率分析当使用邻接矩阵存储图时，Prim算法的时间复杂度为O(n2)，其中n是顶点的数量。这是因为Prim算法需要遍历每个顶点，并在每次迭代中找到与当前生成树最近的顶点。当使用邻接表存储图时，Prim算法的时间复杂