vlambda博客
学习文章列表

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

☝☝☝ 软件工程考研独家平台


撰稿 | 康康哥

编辑 | 丽丽姐

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



双日练: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优化狮