第十五讲图3-数据结构-绍兴文理学院

（第十五讲）绍兴文理学院计算机系计算机应用教研室连通网络的最小代价问题第6章图(3)一、教学目的：明确最小生成树的概念，掌握求最小生成树的prim和kruskal方法及prim求解算法；算法设计训练。二、教学重点：最小生成树的概念，求最小生成树的prim和kruskal方法及prim求解算法；算法设计训练。三、教学难点：求最小生成树的prim算法；算法设计训练。四、教学过程：设G=(V，E)是一个连通网络，U是顶点集V的一个非空子集。若(u，v)是一条具有最小权值(代价)的边，其中u∈U，v∈V-U，则必存在一棵包含边(u，v)的最小生成树。(证明略)§6.4图的应用§6.4.1最小生成树(minimumcostspanningtree)1、最小生成树的概念▲通信网问题。图的顶点之间的边上的权值表示相应的代价，对于n个顶点的连通图可以建立许多不同的生成树。▲一棵生成树的代价就是树上各边的代价之和。▲各边代价之和最小的那棵生成树称为该连通网的最小代价生成树，简称为最小生成树。2、求解最小生成树的基础▲MST性质：uvUV—UTKS400:12▲普里姆(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)TKS500:12(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：TKS600:12(3)普里姆算法的实现①邻接矩阵结构typedefstruct{charvexs[mvnum];intarcs[mvnum][mvnum];intvexnum,arcnum;}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)。TKS700:12v1v2v3v4v5v6105666107121015lowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexkV-T(V)T(V)V6V5V4V3V2Vclosedgev5v11{V2V3V4V5V6}{V1}121510V1V1V12{V3V4V5V6}{V1V2}V2V1V2V2v27156503v3{V4V5V6}{V1V2V3}715600V2V1V24v4{V5V6}{V1V2V3V4}610000V4V46v6{V5}{V1V2V3V4V6}010000V45∮{V1V2V3V4V6V5}00000④示例v1v2v3v4v5v6105666107121015生成树可能不唯一TKS800:12⑤算法描述voidminispantree_prim(amgraphg,charu)//普里姆算法{struct{intadjvex;intlowcost;}closedge[mvnum];inti,j,k,min;k=locatevex(g,u,g.vexnum);//初始化for(j=0;jg.vexnum;j++)if(j!=k){closedge[j].adjvex=k;closedge[j].lowcost=g.arcs[k][j];}closedge[k].lowcost=0;TKS900:12for(i=1;ig.vexnum;i++)//重复n-1次做{min=maxint;for(j=0;jg.vexnum;j++)if(closedge[j].lowcost0&&closedge[j].lowcostmin){min=closedge[j].lowcost;k=j;}printf(%c--%2d--%c,g.vexs[closedge[k].adjvex],closedge[k].lowcost,g.vexs[k]);//输出closedge[k].lowcost=0;//把顶点vexs[k]加入到Tfor(j=0;jg.vexnum;j++)//调整if(g.arcs[k][j]closedge[j].lowcost){closedge[j].adjvex=k;closedge[j].lowcost=g.arcs[k][j];}getch();}}算法6.8普里姆算法S15_1TKS1000:12⑥算法分析时间复杂度：4、克鲁斯卡尔算法(1)克鲁斯卡尔算法的构造过程设连通网络N={V,E},将N中的边按权值从小到大的顺序排列。①最初先构造一个只有n个顶点，没有边的非连通图T={V,},图中每个顶点自成一个连通分量。②在E中选择权值最小的边，若该边依附的两个顶点落在T中不同的连通分量上(即不形成回路)，则将此边加入到T中；否则将此边舍去，重新选择下一条权值最小的边。③重复②，直至T中所有顶点都在同一个连通分量上为止。10101110))1()1(()1(njnjninjOOO)()1()1)(12()1(2)1(21011nOOnnOnOnjniTKS1100:12即(算法步骤)令V(T)=V(G);E(T)=；WHILE(E(T)中的边数＜n-1){从E(G)中选取权数最小的边(vi,vj);IF((vi,vj)在T中不构成圈)加边(vi,vj)到E(T)中；将边(vi,vj)从E(G)中删去;}(2)示例v1v2v3v4v5v6105666107121015v1v2v3v4v5v61056661071210155661010生成树可能不唯一TKS1200:12(3)克鲁斯卡尔算法的实现①辅助数据结构Ⅰ存储边信息的结构体(数组edge)structedgenode{inthead;//边的始点inttail;//边的终点intlowcost;//边上的权值};Ⅱ标识各顶点连通分量数组vexset[arcnum]对每个顶点vi∈V，对应元素vexset[i]表示该顶点所在的连通分量。初始时：vexset[i]=i，表示各顶点自成一个连通分量。TKS1300:12②算法思想Ⅰ将边信息数组edge中的元素按权值从小到大排序。Ⅱ依次从排好序的数组edge中选出一条边(vl，v2)，在vexset中分别查找vl和v2所在的连通分量VS1和VS2。若VS1和VS2不等，表明所选的两个顶点分属不同的连通分量，输出此边，并合并VS1和VS2两个连通分量；若VS1和VS2相等，表明所选的两个顶点属于同一个连通分量，舍去此边而选择下一条权值最小的边。Ⅲ重复Ⅱ(n-1次)，直至edge中所有的边都扫描判断完，并且所有顶点都在同一连通分量上。③算法描述voidminispantree_kruskal(amgraphg){inti,j,v1,v2,vs1,vs2,*vexset;vexset=newint[g.vexnum];TKS1400:12sort(g);for(i=0;ig.vexnum;i++)vexset[i]=i;for(i=0;ig.arcnum;i++){v1=g.edge[i].head;v2=g.edge[i].tail;vs1=vexset[v1];vs2=vexset[v2];if(vs1!=vs2){printf(%c--%2d--%c,g.vexs[v1],g.edge[i].lowcost,g.vexs[v2]);for(j=0;jg.vexnum;j++)if(vexset[j]==vs2)vexset[j]=vs1;}}}算法6.9克鲁斯卡尔算法S15_2TKS1500:12④算法分析时间复杂度：○(n×e)～○(e×loge)(4)比较两种算法比较算法名普里姆算法克鲁斯卡尔算法时间复杂度○(n2)○(n×e)适应范围稠密图稀疏图？五、作业：1、书面作业：P161：2中(1)、(2)、(3)2、实践：实验二、栈序列匹配TKS1600:12