首页 > 试题广场 >

若从顶点 V0 开始对图进行深度优先遍历，则可能得到的不同遍

[单选题]

设有向图 G=(V, E)，顶点集 V={V0, V1, V2, V3}，边集 E={<v0,v1>, <v0,v2>, <v0,v3>, <v1,v3>}。若从顶点 V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是 （） 。 

  • 2
  • 3
  • 4
  • 5
查看正确选项
添加回答
VagrantYang头像 VagrantYang
先把1和3捆绑，A2 2, 3和1还可以交换，所以再乘2，然后3和1还可以不挨着，所以5种
发表于 2018-01-10 19:41:47 回复(0)
二咩头像 二咩
五种分别是132,213,231,312,321
发表于 2016-11-28 08:37:22 回复(0)
倒悬的橙子头像 倒悬的橙子
发表于 2018-01-08 14:41:22 回复(4)
LeoLiu940214头像 LeoLiu940214
为什么会有0321这个顺序，访问完3之后不应该访问1吗？？
发表于 2017-03-21 11:51:12 回复(2)
hackjeremy头像 hackjeremy
有向是5个 无想是4个 审题审题
发表于 2017-09-19 15:48:04 回复(0)
_立夏本夏_头像 _立夏本夏_
请注意！！！不要有人跟我一样，当成了拓扑排序，自然而然地选择了2种。
发表于 2020-06-20 10:02:11 回复(0)
王景润头像 王景润
无向图0213,0231,0132,0312 有向图考虑一下第二步走3的情况
发表于 2019-07-31 09:32:12 回复(0)
牛客、芒果熊头像 牛客、芒果熊
5个，选D
发表于 2022-11-14 15:27:43 回复(0)
JunJ_5头像 JunJ_5
相当于问有几个树，左右子树区分。
发表于 2021-11-15 12:09:39 回复(0)
沙月ちゃん头像 沙月ちゃん

我审题有误，一开始我以为遍历的是边，后来看选项才发现遍历的是顶点。

穷举法

{v0,v1,v3,v2}
{v0,v3,v1,v2}
{v0,v2,v1,v3}
{v0,v2,v3,v1}
{v0,v3,v2,v1}
共种，选D。

编辑于 2020-08-04 23:24:08 回复(0)
不做人了头像 不做人了
看成拓扑排序了... 只是图的深度遍历，....是有向图
编辑于 2020-09-14 11:39:11 回复(0)
Forrest_Lin头像 Forrest_Lin
如果是无向图：最后访问V2，V1&V3 A(2,2); 第二个访问V2， V1&V3 A(2,2);
如果是有向图，则还需加上：V0 V3 V2 V1 
发表于 2018-04-25 11:46:04 回复(0)
侯卿头像 侯卿
并不是每条边走完后还有两种选择所以是6种，因为当第一次选择走V1这一条时，剩下的只有一条了。
发表于 2018-04-18 21:48:53 回复(0)
洛比达头像 洛比达

少了个0321.。。。。。。

发表于 2017-09-04 15:48:26 回复(0)
shiyan娃娃头像 shiyan娃娃
一共有5中：<V0,V1,V3,V2>，<V0,V2,V1,V3>，<V0,V2,V3,V1>，<V0,V3,V1,V2>，因为是有向图，所以还有<V0,V3,V2,V1>.
发表于 2017-08-18 17:02:52 回复(0)
Prophet5头像 Prophet5
有向图的遍历，，算法里面有个对节点的循环
发表于 2017-07-07 17:27:52 回复(0)
王道论坛头像 王道论坛

画出该有向图图形如下：


采用图的深度优先遍历，共 5 种可能： <v0, v1, v3, v2> ， <v0, v2, v3, v1> ， <v0, v2, v1, v3> ，<v0, v3, v2, v1> ， <v0, v3, v1, v2> ，选 D 。

发表于 2016-12-13 18:21:18 回复(0)
艾晓米Amyfairy头像 艾晓米Amyfairy

画出该有向图图形如下：

采用图的深度优先遍历，共 5 种可能： <v0, v1, v3, v2> ， <v0, v2, v3, v1> ， <v0, v2, v1, v3> ， <v0, v3, v2, v1> ， <v0, v3, v1, v2> ，选 D 。（来自王道论坛）

发表于 2016-12-01 18:34:02 回复(0)
提交观点

问题信息

图
上传者：城市里的养猫者
难度：
18条回答 10103浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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