搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > CS优化狮 > 计软考研双日练 | 深度优先遍历图的方法是什么?

计软考研双日练 | 深度优先遍历图的方法是什么?

CS优化狮 2020-05-30
☝☝☝ 软件工程考研独家平台


撰稿 | 康康哥

编辑 | 丽丽姐

本文由懂计算机、软件工程的博士师哥原创



双日练:NO.20200526

计软考研双日练 | 深度优先遍历图的方法是什么?

下列选项中,不是图深度优先遍历搜索的是()。


计软考研双日练 | 深度优先遍历图的方法是什么?

A. V1, V5, V4, V3, V2

B. V1, V3, V2, V5, V4

C. V1, V2, V5, V4, V3

D. V1, V2, V3, V4, V5

 


解析:本题考查了深度优先遍历算法。

 

深度优先遍历算法


深度优先遍历图的方法是,从图中某顶点v出发:


(1)访问顶点v;


(2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历直至图中和v有路径相通的顶点都被访问;


(3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。 


图中从v1出发,遍历V2或V3或V5,


第一步:

1.1  V2、V5

1.2  V3、V2

1.3  V5、V4

 

2.1 V2 、V5、 V4

2.2 V3 、V2 、V5

2.3 V5 、V4、 V3

 

3.1 V2 、V5、 V4、V3

3.2 V3 、V2 、V5、V4

3.3 V5 、V4、 V3、V2

 

遍历完只有D不是深度优先。

 

故选D



计软考研双日练 | 深度优先遍历图的方法是什么?
软工博士带你飞
考软工 · 看CS优化狮

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《计软考研双日练 | 深度优先遍历图的方法是什么?》的版权归原作者「CS优化狮」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注CS优化狮微信公众号

CS优化狮微信公众号:CSyouhuashi

CS优化狮

手机扫描上方二维码即可关注CS优化狮微信公众号

CS优化狮最新文章

精品公众号随机推荐

上一篇 >>

Scala学习一