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

《数据结构(牛小飞)2 图的遍历.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图的遍历深度优先搜索广度优先搜索图的遍历小结和作业复习课堂练习图的遍历的应用举例(自学)复习-图的存储结构BACDFE复习-图的存储结构012345ABCDEF14043525011253BACDFE复习-图的存储结构ABECDABECD1597211132复习-图的存储结构ABECD0101234ABCDE32034ABECD159721113201234ABCDE11549320111722123复习-图的存储结构0101234ABCDE32034ABECD图的遍历定义：从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。用途：是解决图的连

2、通性、拓扑排序和求关键路径等算法的基础。深度优先搜索广度优先搜索分类：深度优先搜索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、先搜索得到的顶点序列不是唯一的？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);V1V2V3V4V5V1V2V8V5V6V

4、4V2V8V8V3V1V6V7V3V8DFS(G,V1)V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V7深度优先搜索—非连通图首先将图中每个顶点的访问标志设为fasle,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8深度遍历：V1V2V4V8V5V3V6V7深度优先搜索—非连通图深度优先搜索—非连通图voidDFSTraverse(intv){for(v=0;v

5、lse;//访问标志数组初始化for(v=0;v

6、都被访问到。深度优先搜索—非连通图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.重复上述

7、过程，直至图中所有顶点都被访问到为止广度优先搜索V1V2V4V5V3V7V6V8V1V8广度遍历序列：V4V6V8V2V5V1V3V7V2V3V4V5V6V7广度优先搜索V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V1V8广度遍历序列：V2V3V4V6V7V5publicvoidBFS(){ArrayQueueAQueue=newArrayQueue();for(inti=0;i