首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
无向图G=(V,E),其中:V={a,b,c,d,e,f},
[单选题]
无向图G=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深度优先遍历,得到的顶点序列正确的是()
a,b,e,c,d,f
a,c,f,e,b,d
a,e,b,c,f,d
a,e,d,f,c,b
查看答案及解析
添加笔记
邀请回答
收藏(187)
分享
纠错
6个回答
添加回答
0
推荐
gxynikita
选D。
假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地,用此方法遍历图就很自然地称之为图的深度优先遍历。
深度优先遍历的顺序有a,b,e,d,f,c;a,e,d,f,c,b;a,e,b,d,f,c;a,c,f,d,e,b.
所以选D。
编辑于 2015-02-10 17:12:34
回复(0)
27
Erya_尔雅
首先深度优先遍历的定义:
从同种某个初始顶点
v
出发,首先访问初始顶点
v
,然后选择一与顶点
v
相邻且没有别访问过的顶点
w
为初始顶点,再从
w
出发进行深度优先直到图中与当前顶点
v
邻接的所有顶点都被访问过为止。
所以从a出发,有三种选择:b,e,c
1.选b==>
a,b
,
e,d,f,c
2.选e==>有两种选择:b,d
(1) 选b==>
a,e,b
,
d,f,c
(2) 选d==>
a,e,d,
f,c,b
3.选c==>
a,c,
f,d,e,b
编辑于 2015-12-30 11:25:32
回复(3)
0
细雨微茫
首先深度优先遍历的定义:
从同种某个初始顶点
v
出发,首先访问初始顶点
v
,然后选择一与顶点
v
相邻且没有别访问过的顶点
w
为初始顶点,再从
w
出发进行深度优先直到图中与当前顶点
v
邻接的所有顶点都被访问过为止。
有很多种情况,看选项。每个选项判断下 以a为出发点。邻接点b e c,存在one[]。 one[]随机选一个c,邻接点f 存起来two[]。 two[]随机选一个 f ,邻接点d,存 three[]。 three[]随机选一个 d.无邻接点。返回。 two[] 空,返回。 遍历 one[].
所以,答案为:D
编辑于 2019-08-30 14:34:03
回复(0)
0
友人说201904171536944
d
发表于 2019-05-02 11:13:19
回复(0)
0
现在感觉挺好
有很多种情况,看选项。每个选项判断下
以a为出发点。邻接点b e c,存在one[]。
one[]随机选一个c,邻接点f 存起来two[]。
two[]随机选一个 f ,邻接点d,存 three[]。
three[]随机选一个 d.无邻接点。返回。
two[] 空,返回。
遍历 one[].
为了帮助理解,这样说,用先进后出队列或着栈结构很容易处理。
发表于 2018-07-03 16:42:56
回复(0)
0
锁秋
没看懂
发表于 2016-09-26 09:46:19
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
图
查找
来自:
数据分析工程师考试样卷
难度:
6条回答
187收藏
21204浏览
热门推荐
相关试题
时针,分针在一昼夜的时间内重合次数...
数学运算
评论
(21)
来自
数据分析工程师考试样卷
使用KMP算法在文本串S中找模式串...
查找
评论
(55)
来自
数据分析工程师考试样卷
方差分析的统计原理和运用条件。
百度
数理统计
评论
(1)
来自
数据分析工程师考试样卷
明明的随机数
数组
评论
(3692)
来自
华为研发工程师编程题
已知a
40
=...
京东
职能
2019
财务
保险
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题