数据结构第7章 图3ppt课件

.,1,第七章图,7.1图的类型定义,7.2图的存储结构,7.3图的遍历,7.4最小生成树,7.5有向无环图及其应用,7.6最短路径,.,2,7.3图的遍历,图的遍历：从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组visit0.n-1作为对顶点的标记，当顶点vi未被访问，visiti值为0；当vi已被访问，则visiti值为1。通常，有两种遍历图的路径：深度优先搜索和广度优先搜索，对无向图和有向图都适用。,.,3,图的两种遍历方法：1.深度优先搜索图的深度优先遍历类似于树的先根遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-FirstSearch)。相应地，用此方法遍历图就称之为图的深度优先遍历。2.广度优先搜索广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历就称为广度优先遍历。,.,4,1.深度优先搜索DFS,基本思想：选择图中某个(强)连通分量中某个顶点v出发：访问顶点v，并将其访问标记置为访问过，即visitedv=1；依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历，直到(强)连通分量中和v有路径相通的顶点都被访问过；如果图中还有顶点未被访问，则另选图中其余(强)连通分量中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问过为止。,.,5,.,6,(强)连通分量的遍历：W1、W2和W3均为V的邻接点。SG1为从W1出发可以访问到的顶点集；,SG2为从W2出发可以访问到的顶点集；SG3为从W3出发可以访问到的顶点集。,访问顺序：SG1SG2SG3。交集部分只访问一次。,.,7,.,8,T,T,T,T,T,T,T,T,T,a,c,h,d,k,f,e,b,g,a,c,h,k,f,e,d,b,g,访问标志:,访问次序:,例如:,h,k,.,9,voidDFSTraverse(GraphG)/深度优先遍历for(v=1;v=G.vexnum;+v)visitedv=FALSE;/访问标志数组初始化for(v=1;v=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w,Visit);/DFS,深度优先遍历的递归算法,.,10,例1：深度优先遍历图G，并写出深度优先遍历序列。序列1：V1,V2,V4,V8,V5,V3,V6,V7序列2：V1,V2,V5,V8,V4,V3,V7,V6,注意：由于没有规定访问邻接点的顺序，深度优先序列不是唯一的。,.,11,例2：深度优先遍历图G，并写出深度优先遍历序列。,深度优先遍历序列：,V1,V2,V4,V8,V5,V6,V3,V7,V1,V2,V5,V8,V4,V6,V3,V7,V1,V3,V7,V8,V6,V5,V2,V4,.,12,深度优先遍历序列对图进行深度优先遍历时，按访问顶点的先后次序得到的顶点序列称为该图的深度优先遍历序列，或DFS序列。一个图的DFS序列不一定惟一;源点和存储结构的内容均已确定的图的DFS序列惟一。邻接矩阵表示的图确定源点后，DFS序列惟一；只有给出了邻接表的内容及初始出发点，才能惟一确定其DFS序列,.,13,例3：已知图的邻接表如下，求从顶点0出发的深度优先遍历序列。,深度优先遍历序列：,0,1,2,3,4,深度优先遍历序列：,0,1,2,3,40,1,2,4,30,1,4,2,30,3,2,1,40,3,2,4,1,.,14,例4：已知图的邻接矩阵，求从顶点0出发的深度优先遍历序列。,深度优先遍历序列：,0,1,3,4,2,5,6,.,15,例5：已知图的邻接表如下，求从顶点0出发的深度优先遍历序列。,深度优先遍历序列：,0,1,2,3,.,16,2.广度优先搜索BFS,选择(强)连通分量中的某个顶点vi出发：访问顶点vi，并将其访问标志置为已被访问，即visitedvi=1；访问vi的所有未被访问的邻接点w1,w2,wk；依次从这些邻接点出发，访问它们的所有未被访问的邻接点，直到(强)连通分量的所有顶点都被访问；重复上述步骤，直到图中所有的顶点都被访问。,.,17,对连通图，从起点V到其余各顶点必定存在路径。,其中，Vw1,Vw2,Vw5的路径长度为1；,Vw3,Vw6,Vw8的路径长度为2；,Vw4,Vw7的路径长度为3,各顶点和起点之间存在“远近”关系。就是按照“由近到远”的顺序进行遍历。,.,18,voidBFSTraverse(GraphG,Status(*Visit)(intv)/广度优先非递归遍历。使用辅助队列Q和访问标志数组visited。for(v=1;vG.vexnum;+v)visitedv=FALSE;InitQueue(Q);/置空的辅助队列Qfor(v=1;v=0;w=NextAdjVex(G,u,w)/访问邻接点if(!visitedw)/u的尚未访问的邻接顶点w入队列Qvisitedw=TRUE;(*Visit)(w);EnQueue(Q,w);/if/while/BFSTraverse,.,20,例1：广度优先遍历图G，并写出广度优先遍历序列。广度优先遍历序列：V1,V2,V3,V4,V5,V6,V7,V8,例2：广度优先遍历图G，并写出广度优先遍历序列。广度优先遍历序列：V1,V2,V3,V4,V5,V6,V7,V8,.,21,图的广度优先遍历序列广度优先遍历图所得的顶点序列，定义为图的广度优先遍历序列，简称BFS序列。一个图的BFS序列不一定是惟一的;给定了源点及图的存储结构时，BFS序列就是惟一的。,.,22,例3：已知图的邻接表如下，求从顶点0出发的广度优先遍历序列。,广度优先遍历序列：,0,1,3,2,4,广度优先遍历序列：,0,1,3,2,40,1,3,4,20,3,1,2,4,.,23,例4：已知图的邻接矩阵，求从顶点0出发的广度优先遍历序列。,0,1,2,3,4,6,5,广度优先遍历序列：,.,24,例5：已知图的邻接表如下，求从顶点0出发的广度优先遍历序列。,.,25,例6：画出该网的邻接矩阵。根据画出的邻接矩阵存储结构，从顶点1出发，分别进行深度优先遍历和广度优先遍历；,.,26,123456,123456,深度优先：1，2，5，4，6，3广度优先：1，2，3，5，6，4,.,27,极大连通子图：该子图是无向图D的连通子图，将D的任何不在该子图中的顶点加入，子图不再是连通的；,极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。,若T是G的生成树当且仅当T满足如下条件：1.T是G的连通子图2.T包含G的所有顶点3.T中无回路,7.4最小生成树,.,28,7.4最小生成树,假设要在n个城市之间建立通讯联络网，如何在最节省经费的前提下建立这个通讯网？,问题：,分析：首先，该网必须是连通网；其次，网中的线路必须最少；最后，考虑所有线路的长度之和最小。,最小生成树满足上述要求。,.,29,上述问题等价于：构造网的一棵最小生成树，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和”最小。求最小生成树的两个算法：普里姆算法：适用于求边稠密的网的最小生成树。克鲁斯卡尔算法：适用于求边稀疏的网的最小生成树。,.,30,假设有连通网N=V,E，求N的最小生成树T=TV,TE。,算法的基本思想:,一、普里姆(Prim)算法,令TV=v,TE=；/从一个顶点v开始TE+=min(v,u)，TV+=u，其中,vTV,uV-TV;重复步骤2，直到TV=V。,.,31,取图中任意一个顶点v作为生成树的根，之后往生成树上添加新的顶点w。在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有n个顶点为止。,普里姆算法的基本思想:,.,32,步骤：(1)初始时，U=v0，边集合TE=；(2)在所有v0U、wV-U的边中选择一条权值最小的边，设这条边为（v0,w）；(3)将边(v0,w)加入TE，同时将w加入U中，而把w从V-U中删掉；(4)重复(2)、(3)，直到U=V为止。,.,33,(1)普里姆算法举例,例1使用普里姆算法为图G构造最小生成树。,设最小生成树为：T(U，TE),图G(V,E),构造步骤如下：,.,34,步骤1：初始状态,Uv1TE=V-U=v2,v3,v4,v5,v6,(1)普里姆算法举例,.,35,步骤2：,Uv1,v3V-U=v2,v4,v5,v6,(1)普里姆算法举例,.,36,步骤3：,Uv1,v3,v6V-U=v2,v4,v5,(1)普里姆算法举例,.,37,步骤4：,Uv1,v3,v6,v4V-U=v2,v5,(1)普里姆算法举例,.,38,步骤5：,Uv1,v3,v6,v4,v2V-U=v5,(1)普里姆算法举例,.,39,步骤6：,Uv1,v2,v3,v4,v5,v6UV，结束,(1)普里姆算法举例,.,40,在算法实现中设置一个辅助数组closedege，对当前V-U集合中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边；,structVertexTypeadjvex;/U集中的相邻顶点序号VRTypelowcost;/边的权值closedgeMAX_VERTEX_NUM;,.,41,例如:,所得生成树权值和=14+8+3+5+16+21=67,.,42,a,e,d,c,b,a,a,a,19,14,18,14,例如:,e,12,e,e,8,16,8,d,3,d,d,7,21,3,c,5,5,所得生成树权值和,=14+8+3+5+16+21=67,.,43,例2:,a,e,d,c,b,g,f,14,8,5,3,16,21,所得生成树权值和,=14+8+3+5+16+21=67,.,44,voidMiniSpanTree_P(MGraphG,VertexTypeu)/用Prim算法从顶点u出发构造网G的最小生成树/网G用邻接矩阵表示k=LocateVex(G,u);max=100;for(j=0;jG.vexnum;+j)/辅助数组初始化if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;/初始，TV=ufor(i=1;iG.vexnum;+i)for(n=1;nG.vexnum;+i)if(closedgen.lowcastmax,下页,.,45,printf(“(%c,%c)”,closedgek.adjvex,G.vexsk);/输出最小生成树的一条边closedgek.lowcost=0;/k顶点并入TV集for(j=0;jG.vexnum;+j)/修改顶点的lowcastif(G.arcskj.adjclosedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;/for/MiniSpanTree_P,.,46,练习题1使用普里姆算法为图G构造一棵最小生成树。,.,47,练习题2使用普里姆算法为图G构造一棵最小生成树。,.,48,算法的基本思想：,二、克鲁斯卡尔(Kruskal)算法,假设有连通网N=V,E，求N的最小生成树T=TV,TE。,令TV=V,TE=；/包含所有顶点TE+=min(v,u),(v,u)是顶点v,u之间的唯一路径;重复步骤2，直到TE中边的条数为n-1。,.,49,算法的基本思想：,考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。,具体做法:先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。,.,50,步骤：(1)最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,)。(2)在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边。(3)依此类推，直至T中所有顶点都在同一连通分量上为止。,.,51,例2用克鲁斯卡尔算法构造图G最的小生成树。,(2)克鲁斯卡尔算法,设最小生成树为：T(U，TE),构造步骤如下：,.,52,步骤1：初始状态,T中只有n个顶点，无边,(2)克鲁斯卡尔算法,.,53,图G=(V,E),步骤2：,T中有n个顶点，1条边,(2)克鲁斯卡尔算法,.,54,图G=(V,E),步骤3