图的深度优先遍历

7.3图的遍历回顾其他数据结构的遍历：•顺序表的遍历•单链表的遍历•二叉树的遍历展望：那么对于图，我们怎样进行遍历呢？•图的深度优先遍历•图的广度优先遍历这两个算法是后面拓扑排序、求关键路径算法的基础7.3.1.连通图的深度优先遍历1.深度优先遍历以v开始的连通图①访问v②分别深度优先遍历v的各个未被访问的邻接点算法描述:2.算法演示01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例图及其邻接表表示演示开始，以v1为遍历的起点01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v101v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v101v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3v201v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v201v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v6v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v6v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v6演示结束3.算法实现从演示过程可以看出，我们必须知道顶点是否已经被访问过。在具体实现时，我们用一个全局数组visited[]来记录顶点是否被访问过。如果visited[i]的值为True，则顶点vi已经被访问，否则没有被访问。3.算法实现VoidDFS（GraphG，intv）{Visited[v]=True；coutv;For(v的每一个邻接点w){If(visited[w]==false)//如果没有被访问过DFS(G,w)}}3.算法实现当图的存储结构为邻接表时，深度优先算法可以表示如下：boolvisited[100]={false};voidDFS(ALGraphmg,intv){visited[v]=true;//以前未被访问，此处被访问／／改变对应的标志为已经访问coutmg.vexs[v].data;／／访问结点vfor(intw=FirstAdjVex(mg,v);w0;w=NextAdjVex(mg,v,w)){／／对于v的每一个邻接点进行考察if(visited[w]==false)／／当该结点未被访问时DFS(mg,w);／／进行深度优先遍历}}练习题：对于下面一个图及其存储结构，写出以v2、v8为起始点的深度优先遍历序列。01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例图及其邻接表表示答案为：以v2为起始点：v2-v1-v3-v6-v7-v4-v8-v5以v8为起始点：v8-v4-v2-v1-v3-v6-v7-v5思考题：若图不是连通图，如何进行深度优先遍历？请建立下图的邻接表结构，并进行深度优先遍历．v1v2v3v4v5v6v7boolvisited[100]={false}；voidDFSTraverse(ALGraphmg){for(inti=1;i=mg.vexnum;i++){if(visited[i]==false)DFS(mg,i);}}