数据结构(牛小飞)2图的遍历.ppt
图的遍历,深度优先搜索,广度优先搜索,图的遍历,小结和作业,复习,课堂练习,图的遍历的应用举例(自学),复习-图的存储结构,复习-图的存储结构,复习-图的存储结构,复习-图的存储结构,复习-图的存储结构,图的遍历,定义：从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。,用途：是解决图的连通性、拓扑排序和求关键路径等算法的基础。,深度优先搜索,广度优先搜索,分类：,深度优先搜索,W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。,深度优先搜索,访问顶点V;for(W1、W2、W3)若邻接点Wi未被访问，则从它出发进行深度优先搜索历。,深度遍历序列：,V1 V2 V4 V8 V5,V6 V3 V7,V1,V2,V4,V5,V3,V7,V6,V8,深度优先搜索-连通图,1、从深度优先搜索遍历连通图的过程类似于树的先根遍历2、对图G深度优先搜索得到的顶点序列不是唯一的？3、搜索过程中经过的边和所有的顶点构成了图的一棵生成树。4、如何判别V的邻接点是否被访问？为每个顶点设立一个“访问标志 visited”;,深度优先搜索-连通图,void DFS(int v)/从顶点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,深度遍历：,V1 V2 V4 V8,V5,V3 V6 V7,深度优先搜索非连通图,深度优先搜索非连通图,void DFSTraverse(int v)for(v=0;vvexNum;+v)vertexsv.visited=false;/访问标志数组初始化 for(v=0;vvexNum;+v)if(!vertexsv.visited)DFS(v);/对尚未访问的顶点调用DFS,T,T,T,T,T,T,T,T,T,a,c,h,d,f,k,e,b,g,a,c,h,f,k,e,d,b,g,访问标志:,访问次序:,例如:,a,c,h,d,f,e,k,b,g,1.从图中某个顶点V0 出发，访问此顶点。,2.然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有与V0有路径的顶点都被访问到。,3.如果图中还有顶点未被访问，则令选一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到。,深度优先搜索非连通图,对连通图，从起始点V到其余各顶点必定存在路径。其中，,V-w1,V-w2,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,V2 V3,V4 V5 V6 V7,广度优先搜索,V1,V2,V4,V5,V3,V7,V6,V8,V1,V8,广度遍历序列：,V2 V3,V4,V6 V7,V5,public void BFS()ArrayQueue AQueue=new ArrayQueue();for(int i=0;i=0;w=nextAdjVex(u,w)if(vertexs(w).wasVisited=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,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b,a,b,e,d,c,f,2：已知一无向图G=（V，E），其中V=a,b,c,d,e E=(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,且得到的结点访问序列为:b a c h d e k f g,假设找到的第一个邻接点是g,则得到的结点访问序列为:b g f k e a d h c,图的遍历应用举例,1.从顶点 i 到顶点s,若存在路径，则从顶点 i 出发进行深度优先搜索，必能搜索到顶点s。,4.简单路径可能有多条。,3.由它出发进行的深度优先遍历已经完成的顶点不是路径上的顶点。,结论：,2.遍历过程中搜索到的顶点不一定是路径上的顶点。,图的遍历应用举例,void DFSearch(int v,int s,char*PATH)/从第v个顶点出发递归地深度优先遍历图G，/求得一条从v到s的简单路径，并记录在PATH中 vertexsv.visited=true;=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个顶点加入路径,&!found,if(w=s)found=TRUE;Append(PATH,w);else,if(!found)Delete(PATH);/从路径上删除顶点 v,图的遍历应用举例,2.求两个顶点之间的一条长度最短的路径,若两个顶点之间存在多条路径，则其中必有一条路径长度最短的路径。如何求得这条路径?,图的遍历应用举例,求从顶点b到顶点k的一条路径长度最短的路径。,图的遍历应用举例,a,b,c,h,d,e,k,f,g,广度优先搜索访问顶点的次序是按“路径长度”渐增的次序。,广度优先搜索是使用“队列”实现的，如何记住路径的所有结点？,小结和作业,图的遍历定义、用途,图的深度优先搜索：拓扑排序,图的广度优先搜索：最短路径,图的遍历方法,课下练习：教材P239图9-4的广度优先搜索和深度优先搜索序列,
