数据结构2-图的遍历ppt课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,图的遍历,深度优先搜索,广度优先搜索,图的遍历,小结和作业,复习,课堂练习,图的遍历的应用举例,(,自学,),图的遍历深度优先搜索广度优先搜索图的遍历小结和作业复习课堂练,1,复习,-,图的存储结构,B,A,C,D,F,E,复习-图的存储结构BACDFE,2,复习,-,图的存储结构,0,1,2,3,4,5,A,B,C,D,E,F,1,4,0,4,3,5,2,5,0,1,1,2,5,3,B,A,C,D,F,E,复习-图的存储结构012345ABCDEF140435250,3,复习,-,图的存储结构,A,B,E,C,D,A,B,E,C,D,15,9,7,21,11,3,2,复习-图的存储结构ABECDABECD1597211132,4,复习,-,图的存储结构,A,B,E,C,D,0,1,0,1,2,3,4,A,B,C,D,E,3,2,0,3,4,A,B,E,C,D,15,9,7,21,11,3,2,0,1,2,3,4,A,B,C,D,E,1 15,4 9,3 2,0 11,1 7,2 21,2 3,复习-图的存储结构ABECD0101234ABCDE3203,5,复习,-,图的存储结构,0,1,0,1,2,3,4,A,B,C,D,E,3,2,0,3,4,A,B,E,C,D,复习-图的存储结构0101234ABCDE32034ABEC,6,图的遍历,定义：,从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。,用途,：,是解决图的连通性、拓扑排序和求关键路径等算法的基础。,深度优先搜索,广度优先搜索,分类：,图的遍历定义：从图中某个顶点出发游历图，访遍图中其余顶点，并,7,深度优先搜索,SG,1,SG,2,SG,3,W,1,、,W,2,和,W,3,均,为,V,的邻接点，,SG,1,、,SG,2,和,SG,3,分别为含顶点,W,1,、,W,2,和,W,3,的子图。,V,w,1,w,3,w,2,深度优先搜索SG1SG2SG3W1、W2和W3 均为 V 的,8,深度优先搜索,SG,1,SG,2,SG,3,V,w,1,w,3,w,2,访问顶点,V,;,for(W,1,、,W,2,、,W,3,),若,邻接点,W,i,未被访问,，,则,从它出发进行深度优先搜索历。,深度优先搜索SG1SG2SG3Vw1w3w2访问顶点V;,9,深度遍历序列：,V,1,V,2,V,4,V,5,V,3,V,7,V,6,V,8,V1,V2 V4 V8 V5,V6 V3 V7,V,1,V,2,V,4,V,5,V,3,V,7,V,6,V,8,深度优先搜索,-,连通图,V,4,V,6,V,2,V,5,V,1,V,8,V,3,V,7,深度遍历序列：V1V2V4V5V3V7V6V8V1 V2,10,1,、从深度优先搜索遍历连通图的过程类似于树的先根遍历,2,、对图,G,深度优先搜索得到的顶点序列不是唯一的？,3,、搜索过程中经过的边和所有的顶点构成了图的一棵生成树。,4,、如何判别,V,的邻接点是否被访问？,为每个顶点设立一个,“,访问标志,visited,”,;,深度优先搜索,-,连通图,1、从深度优先搜索遍历连通图的过程类似于树的先根遍历深度优先,11,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);,void DFS(int v)深度优先搜索-连通图 ve,12,V,1,V,2,V,3,V,4,V,5,V,1,V,2,V,8,V,5,V,6,V,4,V,2,V,8,V,8,V,3,V,1,V,6,V,7,V,3,V,8,DFS(G,V,1,),V,1,V,2,V,4,V,5,V,3,V,7,V,6,V,8,V,1,V,2,V,4,V,5,V,3,V,7,V,6,V,8,V,7,V1V2V3V4V5V1V2V8V5V6V4V2V8V8V3,13,深度优先搜索,非连通图,首先将图中每个顶点的访问标志设为,fasle,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。,深度优先搜索非连通图首先将图中每个顶点的访问标志设为 fa,14,V1,V2,V4,V5,V3,V7,V6,V8,V1,V2,V4,V5,V3,V7,V6,V8,深度遍历：,V1,V2 V4 V8,V5,V3 V6 V7,深度优先搜索,非连通图,V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6,15,深度优先搜索,非连通图,void,DFSTraverse(int v),for,(v=0;vvexNum;,+,v),vertexsv.visited,=false;,/,访问标志数组初始化,for,(v=0;vw,1,V-w,2,V-w,8,的路径长度为,1;,V-w,7,V-w,3,V-w,5,的,路径长度为,2,;,V-w,6,V-w,4,的路径长度为,3,。,w,1,w,8,w,3,w,7,w,6,w,2,w,5,w,4,广度优先搜索,Vw1w8w3w7w6w2w5w4对连通图，从起始点V到其余,19,广度优先搜索,1.,从图中的某个顶点,V,0,出发，并在访问此顶点之后,依次访问,V,0,的所有未被访问过的邻接点,2.,然后,按这些顶点被访问的先后次序依次访问它们的邻接点,，直至图中所有和,V,0,有路径相通的顶点都被访问到。,3.,若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,4.,重复上述过程，直至图中所有顶点都被访问到为止,广度优先搜索1.从图中的某个顶点V0出发，并在访问此顶点之后,20,广度优先搜索,V,1,V,2,V,4,V,5,V,3,V,7,V,6,V,8,V1,V8,广度遍历序列：,V,4,V,6,V,8,V,2,V,5,V,1,V,3,V,7,V2 V3,V4 V5 V6 V7,广度优先搜索V1V2V4V5V3V7V6V8V1V8广度遍,21,广度优先搜索,V1,V2,V4,V5,V3,V7,V6,V8,V1,V2,V4,V5,V3,V7,V6,V8,V1,V8,广度遍历序列：,V2 V3,V4,V6 V7,V5,广度优先搜索V1V2V4V5V3V7V6V8V1V2V4V5,22,public void BFS(),ArrayQueue AQueue=,new ArrayQueue();,for(int i=0;ivexnum;i+),vertexsi.visited=,false;,for(int v=0;v=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,public void BFS(),23,课堂练习,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),，对该图进行深度优先遍历，得到的顶点序列正确的（）。,A,a,b,e,c,d,f B,a,c,f,e,b,d,C,a,e,b,c,f,d D,a,e,d,f,c,b,a,b,e,d,c,f,课堂练习1：无向图G=(V,E),其中：V=a,b,c,d,24,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,2：已知一无向图G=（V，E），其中V=a,b,c,d,e,25,图的遍历应用举例,1.,求一条,从顶点,i,到顶点,s,的简单路径,2.,求两个顶点之间的一条,长度最短,的路径,图的遍历应用举例1.求一条从顶点i到顶点s的简单路径2.求两,26,图的遍历应用举例,1.,求一条,从顶点,i,到顶点,s,的简单路径,求从顶点,b,到顶点,k,的一条简单路径。,a,b,c,h,d,e,k,f,g,从顶点,b,出发进行深度优先搜索遍历,图的遍历应用举例1.求一条从顶点i到顶点s的简单路径求从顶点,27,图的遍历应用举例,求从顶点,b,到顶点,k,的一条简单路径。,假设找到的第一个邻接点是,a,且,得到的结点访问序列为,:,b,a,c h d,e,k,f g,假设找到的第一个邻接点是,g,则得到的结点访问序列为,:,b,g f,k,e,a,d,h,c,a,b,c,h,d,e,k,f,g,图的遍历应用举例求从顶点b到顶点k的一条简单路径。假设找到的,28,图的遍历应用举例,1.,从顶点,i,到顶点,s,若存在路径，则从顶点,i,出发进行深度优先搜索，必能搜索到顶点,s,。,4.,简单路径可能有多条。,3.,由它出发进行的深度优先遍历已经完成的顶点不是路径上的顶点。,结论：,2.,遍历过程中搜索到的顶点不一定是路径上的顶点。,图的遍历应用举例1.从顶点 i 到顶点s,若存在路径，则,29,图的遍历应用举例,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,图的遍历应用举例void DFSearch(int v,30,图的遍历应用举例,2.,求两个顶点之间的一条,长度最短,的路径,若两个顶点之间存在多条路径，则其中,必有一条路径长度最短,的路径。如何求得这条路径,?,图的遍历应用举例2.求两个顶点之间的一条长度最短的路径,31,图的遍历应用举例,a,b,c,h,d,e,k,f,g,求从顶点,b,到顶点,k,的一条路径长度最短的路径。,图的遍历应用举例abchdekfg求从顶点b到顶点k的一条路,32,图的遍历应用举例,a,b,c,h,d,e,k,f,g,a,b,c,h,d,e,k,f,g,广度优先搜索访问顶点的次序是按“路径长度”渐增的次序,。,广度优先搜索是使用“队列”实现的，如何记住路径的所有结点？,图的遍历应用举例abchdekfgabchdekfg广度优先,33,小结和作业,图的遍历定义、,用途,图的深度优先搜索：,拓扑排序,图的广度优先搜索：,最短路径,图的遍历方法,课下练习：,教材,P,239,图,9-4,的广度优先搜索和深度优先搜索序列,小结和作业图的遍历定义、用途图的深度优先搜索：拓扑排序图的广,34,