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

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复习复习- -图的存储构造图的

2、存储构造ABECD0101234ABCDE32034ABECD159721113201234ABCDE1 154 93 20 111 72 212 3复习复习- -图的存储构造图的存储构造0101234ABCDE32034ABECD图的遍历图的遍历定义：从图中某个顶点出发游历图，访遍图中其他顶点，并且使图中的每个顶点仅被访问一次的过程。用途：是处理图的连通性、拓扑排序和求关键途径等算法的根底。u深度优先搜索u广度优先搜索分类：深度优先搜索深度优先搜索SG1SG2SG3W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。Vw1w3w2深度优先搜

3、索深度优先搜索SG1SG2SG3Vw1w3w2访问顶点访问顶点V ;V ;for (W1for (W1、W2W2、W3 )W3 )假设邻接点假设邻接点WiWi未被访未被访问，那么从它出发进问，那么从它出发进展深度优先搜索历。展深度优先搜索历。深度遍历序列：深度遍历序列：V1V2V4V5V3V7V6V8V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8深度优先搜索深度优先搜索- -连通图连通图 V4V6V2V5V1V8V3V71、从深度优先搜索遍历连通图的过程类似于树的先根遍历2、对图G深度优先搜索得到的顶点序列不是独一的？3、搜索过程中经过的边和一切的顶点构成了图的

4、一棵生成树。4、如何判别V的邻接点能否被访问？ 为每个顶点设立一个“访问标志 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);V1V2V3V4V5V1V2V8V5V6V4V2V

5、8V8V3V1V6V7V3V8DFS(G, V1)V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V7深度优先搜索深度优先搜索非连通图非连通图首先将图中每个顶点的访问标志设为 fasle, 之后搜索图中每个顶点，假设未被访问，那么以该顶点为起始点，进展深度优先搜索遍历，否那么继续检查下一顶点。V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8深度遍历：深度遍历：V1 V2 V4 V8V5V3 V6 V7深度优先搜索深度优先搜索非连通图非连通图深度优先搜索深度优先搜索非连通图非连通图void DFSTraverse(int v) for (v=0; vvexNum;

6、 +v) vertexsv.visited = false; / 访问标志数组初始访问标志数组初始化化 for (v=0; vw1, V-w2, V-w8 的的途径长度为途径长度为1;V-w7, V-w3, V-w5的的途径长度为途径长度为2;V-w6, V-w4的途径长度为的途径长度为3。w1w8w3w7w6w2w5w4广度优先搜索广度优先搜索广度优先搜索广度优先搜索1.1.从图中的某个顶点从图中的某个顶点V0V0出发，并在访问此顶点出发，并在访问此顶点之后依次访问之后依次访问V0V0的一切未被访问过的邻接点的一切未被访问过的邻接点2.2.然后按这些顶点被访问的先后次序依次访问然后按这些顶点

7、被访问的先后次序依次访问它们的邻接点，直至图中一切和它们的邻接点，直至图中一切和V0V0有途径相通有途径相通的顶点都被访问到。的顶点都被访问到。3.3.假设此时图中尚有顶点未被访问假设此时图中尚有顶点未被访问, ,那么另选那么另选图中一个未曾被访问的顶点作起始点图中一个未曾被访问的顶点作起始点4.4.反复上述过程，直至图中一切顶点都被访问反复上述过程，直至图中一切顶点都被访问到为止到为止广度优先搜索广度优先搜索V1V2V4V5V3V7V6V8V1V8广度遍历序列：广度遍历序列：V4V6V8V2V5V1V3V7 V2 V3 V4 V5 V6 V7广度优先搜索广度优先搜索V1V2V4V5V3V7V

8、6V8V1V2V4V5V3V7V6V8V1V8广度遍历序列：广度遍历序列： V2 V3 V4 V6 V7V5public 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

9、); /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,babedcf2：知一无向图G=V，E，其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点a开场遍历图，得到的序列为abecd，那么采用的是_。课堂练习课堂练习adbec图

10、的遍历运用举例图的遍历运用举例1.1.求一条从顶点求一条从顶点i i到顶点到顶点s s的简单途径的简单途径2.2.求两个顶点之间的一条长度最短的途径求两个顶点之间的一条长度最短的途径图的遍历运用举例图的遍历运用举例1.1.求一条从顶点求一条从顶点i i到顶点到顶点s s的简单途径的简单途径求从顶点b到顶点k的一条简单途径。abchdekfg从顶点b出发进展深度优先搜索遍历图的遍历运用举例图的遍历运用举例求从顶点b到顶点k的一条简单途径。假设找到的第一个邻接点是a,且得到的结点访问序列为: b a c h d e k f g假设找到的第一个邻接点是g,那么得到的结点访问序列为:b g f k e

11、 a d h cabchdekfg图的遍历运用举例图的遍历运用举例1. 从顶点从顶点 i 到顶点到顶点s ,假设存在途径，那么从顶假设存在途径，那么从顶点点 i 出发进展深度优先搜索，必能搜索到顶点出发进展深度优先搜索，必能搜索到顶点s 。4. 简单途径能够有多条。简单途径能够有多条。3. 由它出发进展的深度优先遍历曾经完成的由它出发进展的深度优先遍历曾经完成的顶点不是途径上的顶点。顶点不是途径上的顶点。结论：结论：2. 遍历过程中搜索到的顶点不一定是途径上的遍历过程中搜索到的顶点不一定是途径上的顶点。顶点。图的遍历运用举例图的遍历运用举例void DFSearch( int v, int s

12、, 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个顶点参与途径&!foundif (w=

13、s) found = TRUE; Append(PATH, w); else if (!found) Delete (PATH); / 从途径上删除顶点从途径上删除顶点 v 图的遍历运用举例图的遍历运用举例2.2.求两个顶点之间的一条长度最短的途求两个顶点之间的一条长度最短的途径径 假设两个顶点之间存在多条途径，那么其中必有一条途径长度最短的途径。如何求得这条途径?图的遍历运用举例图的遍历运用举例abchdekfg求从顶点b到顶点k的一条途径长度最短的途径。图的遍历运用举例图的遍历运用举例abchdekfgabchdekfg广度优先搜索访问顶点的次序是按广度优先搜索访问顶点的次序是按“途途径长度渐增的次序。径长度渐增的