图的深度优先遍历ppt课件.ppt

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,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,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,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的每一个邻接点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);,