图的深度优先遍历

《图的深度优先遍历》由会员分享，可在线阅读，更多相关《图的深度优先遍历（54页珍藏版）》请在金锄头文库上搜索。

1、7.3图的遍历回顾其他数据结构的遍历：顺序表的遍历单链表的遍历二叉树的遍历展望：那么对于图，我们怎样进行遍历呢？图的深度优先遍历图的广度优先遍历这两个算法是后面拓扑排序、求关键路径算法的基础7.3.1.连通图的深度优先遍历1.深度优先遍历以v开始的连通图访问v分别深度优先遍历v的各个未被访问的邻接点算法描述算法描述:2.算法演示01 v12 v23 V34 V45 v56 v67 v78 v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例图及其邻接表表示演示开始，以v1为遍历的起点01v12v23V34V45v56v67v78v8v2

2、v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v101v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v101v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3v201v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v201v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4

3、v5, v1v3, v2v1v5v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2

4、v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v

5、4v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v801v12v23V34V45v5

6、6v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v801v12v23V34V45v56v67v78v8v2v3v1

7、v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v

8、2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4

9、v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v6v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v6v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v

10、8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v701v12v23V34V45v56v6

11、7v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5

12、v2v8, v3v1v7, v6v3, v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v

13、8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v

14、601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v6演示结束3.算法实现 从演示过程可以看出，我们必须知道顶点是否已经被访问过。在具体实现时，我们用一个全局数组visited来记录顶点是否被访问过。如果visitedi的值为True，则顶点vi已经被访问，否则没有被访问。3.算法实现Void DFS（Graph G，int v）Visitedv=True；coutv;For(v的每一个邻接点w)If(visitedw

15、=false)/如果没有被访问过DFS(G,w)3.算法实现当图的存储结构为邻接表时，深度优先算法可以表示如下：bool visited100=false;void DFS(ALGraph mg,int v)visitedv=true;/以前未被访问，此处被访问改变对应的标志为已经访问coutmg.vexsv.data0;w=NextAdjVex(mg,v,w)对于v的每一个邻接点进行考察if(visitedw=false)当该结点未被访问时DFS(mg,w);进行深度优先遍历练习题：对于下面一个图及其存储结构，写出以v2、v8为起始点的深度优先遍历序列。01 v12 v23 V34 V45

16、v56 v67 v78 v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例图及其邻接表表示答案为：以v2为起始点：v2-v1-v3-v6-v7-v4-v8-v5以v8为起始点：v8-v4-v2-v1-v3-v6-v7-v5思考题：若图不是连通图，如何进行深度优先遍历？请建立下图的邻接表结构，并进行深度优先遍历v1v2v3v4v5v6v7bool visited100=false；void DFSTraverse(ALGraph mg)for(int i=1 ;i=mg.vexnum;i+)if(visitedi=false) DFS(mg,i);