我要招人

去企业版

首页 > 试题广场 >

无向图 G = (V, E)，其中 V = {a, b, c

[不定项选择题]

无向图 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出发可以得到一种深度优先遍历的顶点序列为（）。

```
abedfc
```
```
acfebd
```
```
aebdfc
```
```
aedfcb
```

查看正确选项

白起丶

我就想知道D选项，对于一个有向图来说也可以回溯吗？

发表于 2020-07-05 11:34:33 回复(0)

安安634004167

编辑于 2017-06-17 21:06:57 回复(1)

不做人了

ACD 答案错了

发表于 2020-06-30 09:10:15 回复(3)

zerone-Wong

我认为答案是对的。题目不是让你找出一条一通到底、所有字母全覆盖的dfs，而且让你找出dfs的遍历序列，也就是说你对某条通路搜索过一遍了，如果还存在其他顶点没有被搜索到的话还要继续搜索另一条路了，直到所有顶点都被搜过为止才算是一种。例如D答案：从(a,e)开始搜，得到情况是a->e->d->f->c，这是一条路，这时还有b没有搜，继续执行(a,b)，所以顶点序列aedfcb也是一种。

发表于 2018-01-23 00:54:32 回复(3)

热心網友

题目应该是得不到的序列，故选B

发表于 2020-12-24 16:25:02 回复(0)

小辫儿-陌上

同志们，题目说了是有向图，所以答案是对的。万万没想到有向图竟然用小括号。。。。

发表于 2019-10-22 21:26:47 回复(1)

电话亭的汽水

深度优先遍历得到的不一定只是一棵树，可能是森林，因为图包括多个连通域

发表于 2017-10-31 19:01:04 回复(0)

香脆豆

这个题选A吧？

发表于 2017-05-26 16:55:54 回复(0)

lxx13

这个图时无向图吗？无向图的话除了b都对如果是有向图就选A吧？

发表于 2017-06-03 16:29:22 回复(1)

韶华偷者

认为答案错误的，要好好区分一点：在边集中，序偶列和线性表的表示不同而且意义不同：

序偶："<a，b>",规定只能由a---->b,而不能反过来。

线性表的表示方法：（a，b），可以表示a到b，也表示b到a。

此道题答案无错误，没有任何歧义。

发表于 2020-02-28 20:52:12 回复(2)

阳光下

答案有误，应该是A e一定要在b之后，那么，BCD选项皆错，

发表于 2017-09-14 15:20:26 回复(8)

zurp

A.abedfc；B.acfebd；C.aebdfc；D.aedfcb

对于C，<a,e><b,e><e,d><d,f><f,c>难度不是这个？走到<b,e>的时候，b的邻居访问完了，退回访问e的未访问邻居d，然后f,c

发表于 2018-04-08 22:02:31 回复(0)

WendellBerry

我真服了，为啥我看到的题目是：

无向图 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出发可以得到一种深度优先遍历的顶点序列为（）。 应该选ACD

为啥有人看到的题目是有向图？？

发表于 2021-12-05 17:46:14 回复(2)

救赎i_

这题的解题思路是这样，按照题目给定的序列，从某一点开始dfs探索，优先探索与序列匹配的顶点，只有与该顶点相连的顶点都被探索了或者没有与之相连的顶点了，才进行回溯，主要分析为什么B错：从a开始出发，a可以到c，c可以到f，f不可以到e，与f相连的顶点还有d没有探索，只能探索d，所以选项B中e在f后面就错了。

发表于 2022-07-28 19:18:50 回复(0)