图的深度优先遍历

上传人:工**** 文档编号:579823179 上传时间:2024-08-27 格式:PPT 页数:54 大小:1.42MB
返回 下载 相关 举报
图的深度优先遍历_第1页
第1页 / 共54页
图的深度优先遍历_第2页
第2页 / 共54页
图的深度优先遍历_第3页
第3页 / 共54页
图的深度优先遍历_第4页
第4页 / 共54页
图的深度优先遍历_第5页
第5页 / 共54页
点击查看更多>>
资源描述

《图的深度优先遍历》由会员分享,可在线阅读,更多相关《图的深度优先遍历(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);

展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 高等教育 > 研究生课件

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号