无向图G=（V E），其中V={a,b,c,d,e,f},E_

推荐

luck

正确答案是D。

DFS算法的特点是从根顶点出发，

1. 访问所到达的顶点v。

2. 前往v的未被访问的邻接点。

若v的所有邻接点均被访问过，则回溯到访问历史中v的上一个顶点v'，对其进行第2步，即访问v'除v之外的其他邻接点；这种回溯可以一直到根顶点；若回溯到根顶点后仍有节点未被访问，且不与根顶点邻接，则更换根节点。

如下图所示，

A. a, b, e, c, d, f

a->b, 没问题；到b后，b的邻接点中只剩下e未被访问，b->e没问题

e->c，不行，e此时仍有未被访问的邻接点d, 且e没有跟c连通，答案错误

B. a, c, f, e, b, d

a->c->f, 没问题；f->e，不行，f此时仍有未被访问的邻接点d，且f没有跟e连通，答案错误

C. a, e, b, c, f, d

a->e->b，没问题；到b后，b的邻接点均被访问，应回溯到e，然后访问e其他未被访问的邻接点（只剩d），且b没有跟c连通，答案错误

D. a, e, d, f, c, b

a->e->d->f->c，没问题；到c后，其两个邻接点a与f均已被访问，按c->f->d->e->a回溯时候发现，e顶点仍有未被访问的顶点b，于是a->e->d->f->c->b

编辑于 2016-02-23 13:03:28 回复(8)

山高太太

DFS深度优先遍历从一个顶点出发：依次对访问过的顶点做标记，并寻找没有访问过的相邻顶点，找直接相连的点，依次找，找到尽头时，再往回溯。

ABC正确答案应为：

A:abedfc

B:acfdeb

C:aebdfc

发表于 2015-09-29 10:11:21 回复(0)

bitcoffee

访问图的时候从根节点开始，依次将节点压入栈，当某个节点不存在没有访问过的相邻节点时开始回溯，所以ABC都不行，C错在访问完b后，应该回溯至e，接着从e进行遍历，而它回溯到a去了，C正确的应该是aebdfc或者aebdcf

发表于 2015-08-12 20:48:44 回复(0)

王华1964

这个题目错误，没有一个选项是正确的！

发表于 2017-04-29 15:07:43 回复(0)

go8

用有向图的边表示法表示无向图的边，这是恶作剧吗？

发表于 2017-02-28 16:54:54 回复(0)

牛客-007

答案：C

深度优先（DFS）遍历的思想是沿着一条路走，一直到走不通的时候再回溯。

首先是结点a,与a相连的有b,c,e,首先选择结点e,e后面没有了，就回溯到a,

然后选择结点b，b后面也没有了，就回溯到a,

然后选结点c,与c相连的有f，与f相连的有d

所以顺序是aebcfd

发表于 2015-01-12 17:01:21 回复(7)

等待一朵花开

题目有问题E代表的是有向边的表示啊！

发表于 2016-07-01 21:07:58 回复(0)

holdtoday

DFS深度优先遍历从一个顶点出发：依次对访问过的顶点做标记，并寻找没有访问过的相邻顶点，

当标记过后的某个顶点没有无访问相邻顶点时，开始回溯，以下使用（# 代表访问标记）

从a出发：

1、a ——b_e_d_f_c_(a#)_(依次回溯至 f#,d#,e#,b#,a#均没有遗漏顶点) 完毕：abedfc;

2、a——c_f_d_e_{a#,}_b_(依次回溯无其他无访问顶点)，完毕：acfedb;

3、a——e_d_f_c_{a#,回溯f#_d#_e#}_b,完毕：aedfcb;

4、a——e_b_{a#,回溯e#}_d_f_c_{回溯其他无遗漏顶点}，aebdfc;

综上：只有D正确。

发表于 2015-09-05 17:26:13 回复(0)

sota_episode

DFS是不是有多种遍历顺序？

发表于 2023-04-24 23:10:38 回复(0)

🍉Mr.Lew

无向图不应该是圆括号(点，点)吗

发表于 2018-10-01 16:43:25 回复(0)

云姐姐

直接看能不能流通就可以了😁

发表于 2016-09-07 15:17:30 回复(0)

沉落的泰坦尼克号

D DFS深度优先遍历从一个顶点出发：依次对访问过的顶点做标记，并寻找没有访问过的相邻顶点.

                a
  e      b          c

 d     f

发表于 2016-02-23 12:59:49 回复(0)

活力雪涵

注意是深度优先遍历，而不是层次遍历，C选项可以是层次遍历的一种。深度优先遍历的思想是沿着一条路走，一直到走不通的时候再回溯。

发表于 2015-09-12 16:36:21 回复(0)

ccpot

主意题目中是无向图，虽然故意用有向边的表示法

发表于 2015-08-12 17:26:14 回复(0)

小小学生

A应该是a,b,e,d,f,c

B应该是a,c,f,d,e,b

C应该是a,e,d,f,c,b

D正确

发表于 2015-07-24 13:18:55 回复(2)

lwya

如果有<e,d>这条边就选择d，否则选c

发表于 2015-07-03 16:19:06 回复(0)

zhy755788055

最后怎么多出来了个,<e,d>,

发表于 2015-05-19 20:48:22 回复(1)

goodlucc

A

发表于 2015-05-18 10:21:50 回复(0)

Sebas

D

深度优先类似于树的前序遍历

发表于 2015-03-15 20:52:40 回复(0)

大明白

D

A: c无法到d

B: f无法到e

C: 不是深度优先

发表于 2015-03-10 16:33:25 回复(0)

无向图G=（V E），其中V={a,b,c,d,e,f},E

问题信息

热门推荐

相关试题