数据结构(牛小飞)2 图的遍历

图的遍历深度优先搜索广度优先搜索图的遍历小结和作业复习课堂练习图的遍历的应用举例(自学)复习-图的存储结构BACDFE010010100011000101001001110000011100复习-图的存储结构012345ABCDEF14043525011253BACDFE复习-图的存储结构ABECD0100100100000101100000100ABECD15972111321593211721复习-图的存储结构ABECD0101234ABCDE32034ABECD159721113201234ABCDE11549320111722123复习-图的存储结构0101234ABCDE32034ABECD图的遍历定义：从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。用途：是解决图的连通性、拓扑排序和求关键路径等算法的基础。深度优先搜索广度优先搜索分类：深度优先搜索SG1SG2SG3W1、W2和W3均为V的邻接点，SG1、SG2和SG3分别为含顶点W1、W2和W3的子图。Vw1w3w2深度优先搜索SG1SG2SG3Vw1w3w2访问顶点V;for(W1、W2、W3)若邻接点Wi未被访问，则从它出发进行深度优先搜索历。深度遍历序列：V1V2V4V5V3V7V6V8V1V2V4V8V5V6V3V7V1V2V4V5V3V7V6V8深度优先搜索-连通图V4V6V2V5V1V8V3V71、从深度优先搜索遍历连通图的过程类似于树的先根遍历2、对图G深度优先搜索得到的顶点序列不是唯一的？3、搜索过程中经过的边和所有的顶点构成了图的一棵生成树。4、如何判别V的邻接点是否被访问？为每个顶点设立一个“访问标志visited”;深度优先搜索-连通图voidDFS(intv){//从顶点v出发，深度优先搜索遍历连通图}//DFS深度优先搜索-连通图vertexs[v].visited=true;//对v的尚未访问的邻接顶点w递归调用DFSfor(w=firstAdjVex(v);w=0;w=nextAdjVex(v,w))if(vertexs[w].visited==false)DFS(w);V1V2V3V4V5V1V2V8V5V6V4V2V8V8V3V1V6V7V3V8DFS(G,V1)V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V7深度优先搜索—非连通图首先将图中每个顶点的访问标志设为fasle,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8深度遍历：V1V2V4V8V5V3V6V7深度优先搜索—非连通图深度优先搜索—非连通图voidDFSTraverse(intv){for(v=0;vvexNum;++v)vertexs[v].visited=false;//访问标志数组初始化for(v=0;vvexNum;++v){if(!vertexs[v].visited)DFS(v);//对尚未访问的顶点调用DFS}}abchdekfg812345670FFFFFFFFF012345678TTTTTTTTTachdfkebgachfkedbg访问标志:访问次序:例如:achdfekbg1.从图中某个顶点V0出发，访问此顶点。2.然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有与V0有路径的顶点都被访问到。3.如果图中还有顶点未被访问，则令选一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到。深度优先搜索—非连通图Vw1w8w3w7w6w2w5w4对连通图，从起始点V到其余各顶点必定存在路径。其中，V-w1,V-w2,V-w8的路径长度为1;V-w7,V-w3,V-w5的路径长度为2;V-w6,V-w4的路径长度为3。w1w8w3w7w6w2w5w4广度优先搜索广度优先搜索1.从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点2.然后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。3.若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点4.重复上述过程，直至图中所有顶点都被访问到为止广度优先搜索V1V2V4V5V3V7V6V8V1V8广度遍历序列：V4V6V8V2V5V1V3V7V2V3V4V5V6V7广度优先搜索V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V1V8广度遍历序列：V2V3V4V6V7V5publicvoidBFS(){ArrayQueueIntegerAQueue=newArrayQueueInteger();for(inti=0;ivexnum;i++)vertexs[i].visited=false;for(intv=0;vvexnum;v++)if(vertexs[v].wasVisited==false){vertexs[v].visited=true;System.out.print(vertexs[v].data+””);AQueue.enQueue(v);while(!AQueue.isEmpty()){u=AQueue.deQueue();for(intw=firstAdjVex(u);w=0;w=nextAdjVex(u,w))if(vertexs(w).wasVisited==false){System.out.print(vertexs[w].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)}，对该图进行深度优先遍历，得到的顶点序列正确的（）。A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,babedcf2：已知一无向图G=（V，E），其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是____________。课堂练习adbec图的遍历应用举例1.求一条从顶点i到顶点s的简单路径2.求两个顶点之间的一条长度最短的路径图的遍历应用举例1.求一条从顶点i到顶点s的简单路径求从顶点b到顶点k的一条简单路径。abchdekfg从顶点b出发进行深度优先搜索遍历图的遍历应用举例求从顶点b到顶点k的一条简单路径。假设找到的第一个邻接点是a,且得到的结点访问序列为:bachdekfg假设找到的第一个邻接点是g,则得到的结点访问序列为:bgfkeadhcabchdekfg图的遍历应用举例1.从顶点i到顶点s,若存在路径，则从顶点i出发进行深度优先搜索，必能搜索到顶点s。4.简单路径可能有多条。3.由它出发进行的深度优先遍历已经完成的顶点不是路径上的顶点。结论：2.遍历过程中搜索到的顶点不一定是路径上的顶点。图的遍历应用举例voidDFSearch(intv,ints,char*PATH){//从第v个顶点出发递归地深度优先遍历图G，//求得一条从v到s的简单路径，并记录在PATH中vertexs[v].visited=true;=TRUE;//访问第v个顶点for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w))if(!Vertexs[w].visited)DFSearch(w,s,PATH);}Append(PATH,getVertex(v));//第v个顶点加入路径&&!foundif(w==s){found=TRUE;Append(PATH,w);}elseif(!found)Delete(PATH);//从路径上删除顶点v图的遍历应用举例2.求两个顶点之间的一条长度最短的路径若两个顶点之间存在多条路径，则其中必有一条路径长度最短的路径。如何求得这条路径?图的遍历应用举例abchdekfg求从顶点b到顶点k的一条路径长度最短的路径。图的遍历应用举例abchdekfgabchdekfg广度优先搜索访问顶点的次序是按“路径长度”渐增的次序。广度优先搜索是使用“队列”实现的，如何记住路径的所有结点？小结和作业图的遍历定义、用途图的深度优先搜索：拓扑排序图的广度优先搜索：最短路径图的遍历方法课下练习：教材P239图9-4的广度优先搜索和深度优先搜索序列