（第十五讲）.ppt

(第十五讲)绍兴文理学院计算机系计算机应用教研室数据结构连通网络的最小代价问题第6章图(3)一、教学目的:明确最小生成树的概念,掌握求最小生成树的prim和kruskal方法及prim求解算法;算法设计训练。二、教学重点:最小生成树的概念,求最小生成树的prim和kruskal方法及prim求解算法;算法设计训练。三、教学难点:求最小生成树的prim算法;算法设计训练。四、教学过程:设G=(V,E)是一个连通网络,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值(代价)的边,其中u∈U,v∈V-U,则必存在一棵包含边(u,v)的最小生成树。(证明略)§§(minimumcostspanningtree)1、最小生成树的概念▲通信网问题。图的顶点之间的边上的权值表示相应的代价,对于n个顶点的连通图可以建立许多不同的生成树。▲一棵生成树的代价就是树上各边的代价之和。▲各边代价之和最小的那棵生成树称为该连通网的最小代价生成树,简称为最小生成树。2、求解最小生成树的基础▲MST性质:uvUV—UTKS**▲普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法是两个利用MST性质构造最小生成树的算法。3、普里姆算法(1)算法思想从连通网络N={V,E}中的某一顶点V(T)={u0}出发,选择与它关联的具有最小权值的边(u0,v),将其以后每一步从一个顶点在V(T)中,而另一个顶点不在V(T)中的各条边中选择权值最小的边(u,v),把它的顶点v加入到集合V(T)中,将其边(u,v)加入到生成树的边集合E(T)中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合V(T)中为止(直到V(T)满n个顶点为止)。顶点v加入到生成树的顶点集合V(T)中,V(T)TKS**(2)算法步骤(构造过程)假设N=(V,E)是连通网,TE是N上最小生成树中边的集合。①U={u0}(u0∈V),TE={}。②在所有u∈U,v∈V-U的边(u,v)∈E中找一条权值最小的边(u0,v0)并入集合TE,同时v0并入U。③重复②,直至U=V为止。此时TE中必有n-l条边,则T=(V,TE)为N的最小生成树。示例1:v1v2v3v4v5v63552461566v5v1v2v3v4v6v1v2v3v4v5v6105666107121015v5v1v2v3v4v6示例2:TKS**(3)普里姆算法的实现①邻接矩阵结构typedefstruct{charvexs[mvnum];intarcs[mvnum][mvnum];intvexnum,um;}amgraph;②记录前驱顶点和V(T)中到V-V(T)权值最小的边的存储空间struct{intadjvex;intlowcost;}closedge[nvnum];③算法实现Ⅰ初始化:首先将初始顶点甜加入U中,对其余的每一个顶点vi,将closedge[i]均初始化为到u的边信息。Ⅱ循环n-l次,做加下处理:a、从各组最小边closedge[v]中选出最小的最小边closedge[k],输出此边(v,k∈V-U);b、将k加入U中;c、更新剩余的每组最小边信息closedge[v],(v∈V-U)。TKS**v1v2v3v4v5v6105666107121015lowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexkV-T(V)T(V)V6V5V4V3V2Vclosedgev5v11{V2V3V4V5V6}{V1}121510V1V1V12{V3V4V5V6}{V1V2}V2V1V2V2v27156503v3{V4V5V6}{V1V2V3}715600V2V1V24v4{V5V6}{V1V2V3V4}610000V4V46v6{V5}{V1V2V3V4V6}010000V45∮{V1V2V3V4V6V5}00000④示例v1v2v3v4v5v6105666107121015生成树可能不唯一TKS**⑤算法描述voidminispantree_prim(amgraphg,charu)//普里姆算法{struct{intadjvex;intlowcost;}closedge[mvnum];inti,j,k,min;k=locatevex(g,u,);//初始化for(j=0;j<;j++)if(j!=k){closedge[j].adjvex=k;closedge[j].lowcost=[k][j];}closedge[k].lowcost=0;TKS**for(i=1;i<;i++)//重复n-1次做{min=ma