图的深度优先遍历ppt课件

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

2、v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v17；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v18；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3v29；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v210；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v

3、1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5v411；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5v412；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v413；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2v814；.01v1

4、2v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2v815；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v816；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4v517；.01v12v23V34V45v56v67v78v8v2v3v1v4v5

5、v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4v518；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v519；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v820；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v

6、8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v821；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v822；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v823；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3

7、v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v824；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v825；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v826；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v

8、3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v827；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v828；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1v3, v2v1v5, v4v2, v8v4, v5v2v829；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6

9、v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v330；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v6v731；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v6v732；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v

10、2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v633；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3v734；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3v735；.01v12v2

11、3V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v736；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v637；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5

12、, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v638；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v639；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v640；.01v12v23V34V45v5

13、6v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v641；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v642；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v

14、2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v643；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v644；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5, v1, v2v1v5, v4v2, v8v4, v5v2v8, v3v1v7, v6v3, v7v3v645；.演示结束46；.3.算法实现 从演示过程可

15、以看出，我们必须知道顶点是否已经被访问过。在具体实现时，我们用一个全局数组visited来记录顶点是否被访问过。如果visitedi的值为True，则顶点vi已经被访问，否则没有被访问。47；.3.算法实现Void DFS（Graph G，int v）Visitedv=True；coutv;For(v的每一个邻接点w)If(visitedw=false)/如果没有被访问过DFS(G,w)48；.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);进行深度优先遍历49；.练习题：对于下面一个图及其存储结构，写出以v2、v8为起始点的深度优先遍历序列。50；.01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例图及其邻接表