图的深度优先遍历.ppt

7.3图的遍历 回顾其他数据结构的遍历： 顺序表的遍历 单链表的遍历 二叉树的遍历 展望： 那么对于图，我们怎样进行遍历呢？ 图的深度优先遍历 图的广度优先遍历 这两个算法是后面拓扑排序、求关键路径算法的基础 7.3.1.连通图的深度优先遍历 1.深度优先遍历以v开始的连通图 访问v 分别深度优先遍历v的各个未被访问的邻接点 2.算法演示 演示开始，以v1为遍历的起点 演示结束 3.算法实现 从演示过程可以看出，我们必须知道顶点是否已经被访问过。在具体实现时，我们用一个全局数组visited[]来记录顶点是否被访问过。如果visited[i]的值为True，则顶点vi已经被访问，否则没有被访问。 3.算法实现 Void DFS（Graph G，int v） { Visited[v]=True；coutv; For(v的每一个邻接点w) { If(visited[w]==false)//如果没有被访问过 DFS(G,w) } } 3.算法实现 当图的存储结构为邻接表时，深度优先算法可以表示如下： bool visited[100]={false}; void DFS(ALGraph mg,int v) { visited[v]=true;//以前未被访问，此处被访问 　　　　　　　　　／／改变对应的标志为已经访问 coutmg.vexs[v].data ; ／／访问结点v for(int w=FirstAdjVex(mg,v);w0;w=NextAdjVex(mg,v,w)) {／／对于v的每一个邻接点进行考察 if(visited[w]==false)／／当该结点未被访问时 DFS(mg,w);／／进行深度优先遍历 } } 练习题： 对于下面一个图及其存储结构，写出以v2、v8为起始点的深度优先遍历序列。 答案为： 以v2为起始点：v2-v1-v3-v6-v7-v4-v8-v5 以v8为起始点：v8-v4-v2-v1-v3-v6-v7-v5 思考题： 若图不是连通图，如何进行深度优先遍历？ 请建立下图的邻接表结构，并进行深度优先遍历． bool visited[100]={false}； void DFSTraverse(ALGraph mg) { for(int i=1 ;i=mg.vexnum;i++) { if(visited[i]==false) DFS(mg,i); } } v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0 v2 v3 v1 v4 v5 v1 v6 v7 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5 , v1 , v2 v1 v5 , v4 v2 , v8 v4 , v5 v2 v8 , v3 v1 v6 v7 v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0 v2 v3 v1 v4 v5 v1 v6 v7 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5 , v1 , v2 v1 v5 , v4 v2 , v8 v4 , v5 v2 v8 , v3 v1 v7 , v6 v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0 v2 v3 v1 v4 v5 v1 v6 v7 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5 , v1 , v2 v1 v5 , v4 v2 , v8 v4 , v5 v2 v8 , v3 v1 v7 , v6 v3 v7 v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0 v2 v3 v1 v4 v5 v1 v6 v7 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5 , v1 , v2 v1 v5 , v4 v2 , v8 v4 , v5 v2 v8 , v3 v1 v7 , v6 v3 v7 v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0 v2 v3 v1 v4 v5 v1 v6 v7 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5 , v1 , v2 v1 v5 , v4 v2 , v8 v4 , v5 v2 v8 , v3 v1 v7 , v6 v3 , v7 v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0 v2 v3 v1 v4 v5 v1 v6 v7 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5 , v1 , v2 v1 v5 , v4 v2 , v8 v4 , v5 v2 v8 , v3 v1 v7 ,