数据结构 第七章 图.ppt

欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2条线路，那么，如何选择n–1条线路使总费用最少？典型用途：先建立数学模型：顶点———表示城市，有n个；边————表示线路，有n–1条；边的权值—表示线路的经济代价；连通网——表示n个城市间的通信网。显然此连通网是一棵生成树！问题抽象：n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST。讨论：如何求得最小生成树？最小生成树（MST）的性质如下：若U集是V的一个非空子集，若(u0,v0)是一条最小权值的边，其中u0?U，v0?V-U；则：(u0,v0)必在最小生成树上。设想一下：先把权值最小的边归入生成树内，逐个递增，舍去回路边，则得到的很可能就是最小生成树！求MST有多种算法，但最常用的是以下两种：Kruskal（克鲁斯卡尔）算法Prim（普里姆）算法Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。Prime算法特点:将顶点归并，与边数无关，适于稠密网。对边操作对顶点操作普里姆(prim)算法基本思路假设N=(V,{E})是连通网,TE是N上最小生成树的边集合:(1)U={u0}(u0V),TE={}(2)在uU,vV-U的边(u,v)E中找一条代价最小的边(u0,v0),TE=TE∪(u0,v0),U=U∪{v0}(3)若U≠V,返回(2)(4)T=(V,{TE})为N的最小生成树.时间复杂度：O(n2),与边数无关例：普里姆(prim)算法描述VoidMiniSpanTree_PRIM(MGraph_G,VertexTypeu){//从u结点出发构造struct{VertexTypeadjvex;//定义辅助数组结构VRTypelowcost;}closedge[MAX_VERTEX_NUM];k=LocateVex(G,u);//求出u结点的序号for(j=0;jG.vexnum;j++)//辅助数组初始化,记录从u到其他顶点的代价信息if(j!=k)closedge[j]={u,G.arcs[k][j].adj};//{adjvex,lowcost}closedge[k].lowcost=0;//表示k已并入U集,U={u};普里姆(prim)算法描述(2)for(i=1;iG.vexnum;i++){k=minimum(closedge);//找出下一个结点printf(closedge[k].adjvex,G.vexs[k]);closedge[k].lowcost=0;//表示k已并入U集for(j=0;jG.vexnum;++j)//修改closedge[j]辅助数组if（G.arcs[k][j].adjclosedge[j].lowcost)closedge[j]={G.vex[k],G.arcs[k][j].adj};//修改{adjvex,lowcost}}}jclosedge12345UV-Uk初态Adjvexlowcost05030170∞0∞{0}{1,2,3,4,5}21Adjvexlowcost0500017220215{0,2}{1,3,4,5}12Adjvexlowcost0000017114215{0,1,2}{3,4,5}43Adjvexlowcost000001710412{0,1,2,4}{3,5}54Adjvexlowcost00000171040{0,1,2,4,5}{3}35Adjvexlowcost00000