首页 > 试题广场 >

无向图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
添加回答
推荐
gxynikita头像 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)
Erya_尔雅头像 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)
细雨微茫头像 细雨微茫
首先深度优先遍历的定义：从同种某个初始顶点 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)
友人说201904171536944头像 友人说201904171536944
d
发表于 2019-05-02 11:13:19 回复(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)
锁秋头像 锁秋
没看懂
发表于 2016-09-26 09:46:19 回复(0)
提交观点

问题信息

图 查找
来自：数据分析工程师考试样卷
难度：
6条回答 21201浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号