《图的深度优先遍历[沐风书苑].ppt》由会员分享，可在线阅读，更多相关《图的深度优先遍历[沐风书苑].ppt（54页珍藏版）》请在三一文库上搜索。
1、7.3图的遍历,回顾其他数据结构的遍历： 顺序表的遍历 单链表的遍历 二叉树的遍历 展望： 那么对于图，我们怎样进行遍历呢？ 图的深度优先遍历 图的广度优先遍历 这两个算法是后面拓扑排序、求关键路径算法的基础,7.3.1.连通图的深度优先遍历,1.深度优先遍历以v开始的连通图,访问v 分别深度优先遍历v的各个未被访问的邻接点,算法描述:,2.算法演示,例图及其邻接表表示,演示开始，以v1为遍历的起点,v1,v3,v2,v3,v3,v1,v5,v4,v3,v1,v5,v4,v3,v1,v5,v3,v1,v5,v2,v8,v3,v1,v5,v2,v8,v3,v1,v5,v2,v3,v1,v5,v2
2、,v4,v5,v3,v1,v5,v2,v4,v5,v3,v1,v5,v2,v4,v3,v1,v5,v2,v4,v2,v8,v3,v1,v5,v2,v4,v2,v8,v3,v1,v5,v2,v4,v2,v8,v3,v1,v5,v2,v4,v2,v8,v3,v1,v5,v2,v4,v2,v8,v3,v1,v5,v2,v4,v2,v8,v3,v1,v5,v2,v4,v2,v8,v3,v1,v5,v2,v4,v2,v8,v3,v1,v5,v2,v4,v2,v8,v3,v1,v5,v2,v4,v2,v8,v1,v5,v2,v4,v2,v8,v1,v5,v2,v4,v2,v8,v1,v6,v7,v1,v5
3、,v2,v4,v2,v8,v1,v6,v7,v1,v5,v2,v4,v2,v8,v1,v7,v1,v5,v2,v4,v2,v8,v1,v7,v3,v7,v1,v5,v2,v4,v2,v8,v1,v7,v3,v7,v1,v5,v2,v4,v2,v8,v1,v7,v3,v1,v5,v2,v4,v2,v8,v1,v7,v3,v3,v6,v1,v5,v2,v4,v2,v8,v1,v7,v3,v3,v6,v1,v5,v2,v4,v2,v8,v1,v7,v3,v3,v6,v1,v5,v2,v4,v2,v8,v1,v7,v3,v3,v6,v1,v5,v2,v4,v2,v8,v1,v7,v3,v3,v6,v1
4、,v5,v2,v4,v2,v8,v1,v7,v3,v3,v6,v1,v5,v2,v4,v2,v8,v1,v7,v3,v3,v6,v1,v5,v2,v4,v2,v8,v1,v7,v3,v3,v6,v1,v5,v2,v4,v2,v8,v1,v7,v3,v3,v6,演示结束,3.算法实现,从演示过程可以看出，我们必须知道顶点是否已经被访问过。在具体实现时，我们用一个全局数组visited来记录顶点是否被访问过。如果visitedi的值为True，则顶点vi已经被访问，否则没有被访问。,3.算法实现,Void DFS（Graph G，int v） Visitedv=True；coutv; For(v的
5、每一个邻接点w) If(visitedw=false)/如果没有被访问过 DFS(G,w) ,3.算法实现,当图的存储结构为邻接表时，深度优先算法可以表示如下： bool visited100=false; void DFS(ALGraph mg,int v) visitedv=true;/以前未被访问，此处被访问 改变对应的标志为已经访问 cout0;w=NextAdjVex(mg,v,w) 对于v的每一个邻接点进行考察 if(visitedw=false)当该结点未被访问时 DFS(mg,w);进行深度优先遍历 ,练习题： 对于下面一个图及其存储结构，写出以v2、v8为起始点的深度优先遍历序列。,例图及其邻接表表示,答案为： 以v2为起始点：v2-v1-v3-v6-v7-v4-v8-v5 以v8为起始点：v8-v4-v2-v1-v3-v6-v7-v5,思考题：,若图不是连通图，如何进行深度优先遍历？ 请建立下图的邻接表结构，并进行深度优先遍历,v1,v2,v3,v4,v5,v6,v7,bool visited100=false； void DFSTraverse(ALGraph mg) for(int i=1 ;i=mg.vexnum;i+) if(visitedi=false) DFS(mg,i); ,