1、图的遍历图的遍历深度优先搜索广度优先搜索图的遍历小结和作业复习课堂练习图的遍历的应用举例(自学)复习复习-图的存储结构图的存储结构BACDFE0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 复习复习-图的存储结构图的存储结构012345ABCDEF14043525011253BACDFE复习复习-图的存储结构图的存储结构ABECD0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 ABECD1597211132复习复习-图的存储结构图的存储结构ABEC
2、D0101234ABCDE32034ABECD159721113201234ABCDE1 154 93 20 111 72 212 3复习复习-图的存储结构图的存储结构0101234ABCDE32034ABECD图的遍历图的遍历定义：从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。用途：是解决图的连通性、拓扑排序和求关键路径等算法的基础。u深度优先搜索u广度优先搜索分类：深度优先搜索深度优先搜索SG1SG2SG3W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。Vw1w3w2深度优先搜索深度优先搜索SG1
3、SG2SG3Vw1w3w2访问顶点访问顶点V;for(W1、W2、W3)若若邻接点邻接点Wi未被访问未被访问，则则从它出发进行深度从它出发进行深度优先搜索历。优先搜索历。深度遍历序列：深度遍历序列：V1V2V4V5V3V7V6V8V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8深度优先搜索深度优先搜索-连通图连通图 V4V6V2V5V1V8V3V71、从深度优先搜索遍历连通图的过程类似于树的先根遍历2、对图G深度优先搜索得到的顶点序列不是唯一的？3、搜索过程中经过的边和所有的顶点构成了图的一棵生成树。4、如何判别V的邻接点是否被访问？为每个顶点设立一个“访问标志
4、visited”;深度优先搜索深度优先搜索-连通图连通图 void DFS(int v)/从顶点v出发，深度优先搜索遍历连通图 /DFS深度优先搜索深度优先搜索-连通图连通图 vertexsv.visited=true;/对v的尚未访问的邻接顶点w递归调用DFSfor(w=firstAdjVex(v);w=0;w=nextAdjVex(v,w)if(vertexsw.visited=false)DFS(w);V1V2V3V4V5V1V2V8V5V6V4V2V8V8V3V1V6V7V3V8DFS(G,V1)V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V7深度优先搜索深度优先搜
5、索非连通图非连通图首先将图中每个顶点的访问标志设为 fasle,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8深度遍历：深度遍历：V1 V2 V4 V8V5V3 V6 V7深度优先搜索深度优先搜索非连通图非连通图深度优先搜索深度优先搜索非连通图非连通图void DFSTraverse(int v)for(v=0;vvexNum;+v)vertexsv.visited=false;/访问标志数组初始化 for(v=0;vw1,V-w2,V-w8 的路的路径长度为径长度为1;V-w
6、7,V-w3,V-w5的的路径长度为路径长度为2;V-w6,V-w4的路径长度为的路径长度为3。w1w8w3w7w6w2w5w4广度优先搜索广度优先搜索广度优先搜索广度优先搜索1.1.从图中的某个顶点从图中的某个顶点V V0 0出发，并在访问此顶点出发，并在访问此顶点之后之后依次访问依次访问V V0 0的所有未被访问过的邻接点的所有未被访问过的邻接点2.2.然后然后按这些顶点被访问的先后次序依次访问按这些顶点被访问的先后次序依次访问它们的邻接点它们的邻接点，直至图中所有和，直至图中所有和V V0 0有路径相通有路径相通的顶点都被访问到。的顶点都被访问到。3.3.若此时图中尚有顶点未被访问若此时
7、图中尚有顶点未被访问,则另选图中则另选图中一个未曾被访问的顶点作起始点一个未曾被访问的顶点作起始点4.4.重复上述过程，直至图中所有顶点都被访问重复上述过程，直至图中所有顶点都被访问到为止到为止广度优先搜索广度优先搜索V1V2V4V5V3V7V6V8V1V8广度遍历序列：广度遍历序列：V4V6V8V2V5V1V3V7 V2 V3 V4 V5 V6 V7广度优先搜索广度优先搜索V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V1V8广度遍历序列：广度遍历序列：V2 V3 V4 V6 V7V5public void BFS()ArrayQueue AQueue=new ArrayQ
8、ueue();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课堂练习课堂练习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)，对该图进行深度优先遍历
9、，得到的顶点序列正确的（）。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,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.1.求一条求一条从顶点从顶点i i到顶点到顶点s s的简单路径的简单路径2.2.求两个顶点之间的一条求两个顶点之间的一条长度最短长度最短的路径的路径图的遍历应用举例图的遍历应用举例1.1.求一条求
10、一条从顶点从顶点i i到顶点到顶点s s的简单路径的简单路径求从顶点b b到顶点k k的一条简单路径。abchdekfg从顶点b b出发进行深度优先搜索遍历图的遍历应用举例图的遍历应用举例求从顶点b b到顶点k k的一条简单路径。假设找到的第一个邻接点是a,a,且且得到的结点访问序列为:b a c h d e k f g假设找到的第一个邻接点是g,则得到的结点访问序列为:b g f k e a d h cabchdekfg图的遍历应用举例图的遍历应用举例1.从顶点 i 到顶点s,若存在路径，则从顶点 i 出发进行深度优先搜索，必能搜索到顶点s。4.简单路径可能有多条。3.由它出发进行的深度优先
11、遍历已经完成的顶点不是路径上的顶点。结论：结论：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
12、个顶点加入路径&!foundif(w=s)found=TRUE;Append(PATH,w);else if(!found)Delete(PATH);/从路径上删除顶点 v 图的遍历应用举例图的遍历应用举例2.2.求两个顶点之间的一条求两个顶点之间的一条长度最短长度最短的路的路径径 若两个顶点之间存在多条路径，则其中必有一条路径长度最短的路径。如何求得这条路径?图的遍历应用举例图的遍历应用举例abchdekfg求从顶点b b到顶点k k的一条路径长度最短的路径。图的遍历应用举例图的遍历应用举例abchdekfgabchdekfg广度优先搜索访问顶点的次序是按广度优先搜索访问顶点的次序是按“路径长度路径长度”渐增的次序渐增的次序。广度优先搜索是使用广度优先搜索是使用“队列队列”实现的，实现的，如何记住路径的所有结点？如何记住路径的所有结点？小结和作业小结和作业图的遍历定义、图的遍历定义、用途用途图的深度优先搜索：图的深度优先搜索：拓扑排序拓扑排序图的广度优先搜索：图的广度优先搜索：最短路径最短路径图的遍历方法图的遍历方法课下练习：课下练习：教材教材P239图9-4的广度优先搜索和深度优先搜索的广度优先搜索和深度优先搜索序列序列
