牛小飞《数据结构》9.2图的遍历

图的遍历,深度优先搜索,广度优先搜索,图的遍历,小结和作业,复习,课堂练习,图的遍历的应用举例(自学),复习-图的存储结构,复习-图的存储结构,复习-图的存储结构,复习-图的存储结构,图的遍历,定义：从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。,用途：是解决图的连通性、拓扑排序和求关键路径等算法的基础。,深度优先搜索,广度优先搜索,分类：,深度优先搜索,W1、W2和W3均为V的邻接点，SG1、SG2和SG3分别为含顶点W1、W2和W3的子图。,深度优先搜索,访问顶点V;for(W1、W2、W3)若邻接点Wi未被访问，则从它出发进行深度优先搜索遍历。,深度遍历序列：,V1V2V4V8V5,V6V3V7,V1,V2,V4,V5,V3,V7,V6,V8,深度优先搜索-连通图,1、从深度优先搜索遍历连通图的过程类似于树的先根遍历2、对图G深度优先搜索得到的顶点序列不是唯一的？3、搜索过程中经过的边和所有的顶点构成了图的一棵生成树。4、如何判别V的邻接点是否被访问？为每个顶点设立一个“访问标志visited”;,深度优先搜索-连通图,voidDFS(intv)/从顶点v出发，深度优先搜索遍历连通图/DFS,深度优先搜索-连通图,vertexsv.visited=true;,/对v的尚未访问的邻接顶点w递归调用DFS,for(w=firstAdjVex(v);w=0;w=nextAdjVex(v,w)if(vertexsw.visited=false)DFS(w);,V1,V2,V3,V4,V5,V1,V2,V8,V5,V6,V4,V2,V8,V8,V3,V1,V6,V7,V3,V8,DFS(G,V1),V7,深度优先搜索非连通图,首先将图中每个顶点的访问标志设为fasle,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。,V1,V2,V4,V5,V3,V7,V6,V8,深度遍历：,V1V2V4V8,V5,V3V6V7,深度优先搜索非连通图,深度优先搜索非连通图,voidDFSTraverse(intv)for(v=0;vw2,V-w8的路径长度为1;,V-w7,V-w3,V-w5的路径长度为2;,V-w6,V-w4的路径长度为3。,w1,w8,w3,w7,w6,w2,w5,w4,广度优先搜索,广度优先搜索,1.从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点,2.然后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。,3.若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,4.重复上述过程，直至图中所有顶点都被访问到为止,广度优先搜索,V1,V8,广度遍历序列：,V4,V6,V8,V2,V5,V1,V3,V7,V2V3,V4V5V6V7,广度优先搜索,V1,V2,V4,V5,V3,V7,V6,V8,V1,V8,广度遍历序列：,V2V3,V4,V6V7,V5,publicvoidBFS()ArrayQueueAQueue=newArrayQueue();for(inti=0;i=0;w=nextAdjVex(u,w)if(vertexs(w).visited=false)System.out.print(vertexsw.data+”);vertexs(w).visited=true;AQueue.enQueue(w);/if/while/if,课堂练习,1：无向图G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的（）。Aa,b,e,c,d,fBa,c,f,e,b,dCa,e,b,c,f,dDa,e,d,f,c,b,a,b,e,d,c,f,2：已知一无向图G=（V，E），其中V=a,b,c,d,eE=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是_。,课堂练习,a,d,b,e,c,图的遍历应用举例,1.求一条从顶点i到顶点s的简单路径,2.求两个顶点之间的一条长度最短的路径,图的遍历应用举例,1.求一条从顶点i到顶点s的简单路径,求从顶点b到顶点k的一条简单路径。,从顶点b出发进行深度优先搜索遍历,图的遍历应用举例,求从顶点b到顶点k的一条简单路径。,假设找到的第一个邻接点是a,且得到的结点访问序列为:bachdekfg,假设找到的第一个邻接点是g,则得到的结点访问序列为:bgfkeadhc,图的遍历应用举例,1.从顶点i到顶点s,若存在路径，则从顶点i出发进行深度优先搜索，必能搜索到顶点s。,4.简单路径可能有多条。,3.由它出发进行的深度优先遍历已经完成的顶点不是路径上的顶点。,结论：,2.遍历过程中搜索到的顶点不一定是路径上的顶点。,图的遍历应用举例,voidDFSearch(intv,ints,char*PATH)/从第v个顶点出发递归地深度优先遍历图G，/求得一条从v到s的简单路径，并记录在PATH中vertexsv.visited=true;/访问第v个顶点for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!Vertexsw.visited)DFSearch(w,s,PATH);,Append(PATH,getVertex(v);/第v个顶点加入路径,Append(PATH,w);else,if(!found)Delete(PATH);/从路径上删除顶点v,图的遍历应用举例,2.求两个顶点之间的一条长度最短的路径,若两个顶点之间存在多条路径，则其中必有一条路径长度最短的路径。如何求得这条路径?,图的遍历应用举例,求从顶点b到顶点k的一条路径长度最短的路径。,图的遍历应用举例,a,b,c,h,d,e,k,f,g,广度优先搜索访问