首页 > 试题广场 >

已知图的邻接表如下所示,根据算法,则从顶点 0 出发按深度优

[单选题]
已知图的邻接表如下所示,根据算法,则从顶点 0 出发按深度优先遍历的结点序列是()

  • 0132
  • 0231
  • 0321
  • 0123
B选项是 0231,但是明显从V3节点没有和V1节点链接,最后一步如何走?
发表于 2018-09-26 15:58:00 回复(1)
邻接表已经给出了,按理来说只有一个答案D,如果单选就选D,这道题是多选,那就假设没给邻接表,根据邻接表得出的图来解题,只有A是不可能的,选BCD
发表于 2020-04-14 11:48:36 回复(1)
先还原图   
   0
/   |  \
1- 2- 3
由图可知,0123、0213、0231、0321都是深度优先遍历的结果
发表于 2019-10-05 15:58:15 回复(1)
直接根据邻接表即可得出,第一行。
发表于 2017-06-29 21:07:42 回复(0)
都有邻接表了,答案还不是唯一的????是我记混了????
发表于 2019-09-05 08:18:10 回复(1)
重新看这个题,直接先根据邻接表还原图:
     0
1 - 2-  3
对该图深度优先搜索
0 1 2 3
0 2 1 3
0 3 2 1
如果在遍历上优先序号最大节点,则:
0 3 2 1
0 2 3 1
0 1 2 3

题外话:题目说的遍历顺序,着实让人不解,实际遍历顺序应该为
0 3 2 1 2 3 1 1 2 3
假如遍历到4个节点的时候,做以记录,则结果只有
0 3 2 1,
其他因为不满足四个节点而无法记录。很奇怪,这样的题目,没意思。

                              
编辑于 2018-07-15 09:33:48 回复(3)
图的遍历,是针对 未访问节点 进行的,所以根据邻接表可以很快得到序列:0123

选D
发表于 2019-02-23 16:00:45 回复(0)
邻接表不唯一是指它在构建的时候不唯一 一旦构建出来之后再遍历就是唯一的
发表于 2022-03-28 09:11:10 回复(0)
邻接表顺序都出来了答案是唯一的。本来昨天入坑,今天已经发现许多答案错误。着实有点怕了
发表于 2019-10-23 12:09:53 回复(1)
阁下认为BCD都可,题目有问题应该改成多选
发表于 2023-04-11 16:43:48 回复(1)
个人理解,邻接表只是图的存储方式,进行深搜的时候每个节点的访问顺序是随机的,从0点开始,可以走1或2或3进行深搜,以此类推,可以得到多颗深度优先树。A错误,因为点1和3中间没有边,故选BCD
发表于 2020-07-09 18:11:49 回复(0)
C选项认真的吗??深度遍历不是相邻未访问的压栈??0和3之间有路径??怎么压的栈??
发表于 2019-02-16 22:31:55 回复(0)
需要注意的是这是一个有向图
发表于 2018-07-11 16:58:22 回复(0)
多选,,,,
发表于 2018-02-17 14:49:10 回复(0)
额,画错了自己  无向01->这里有2可以通过,所以不会回溯到3 必须01->2->3  还有0321 也必须是这个顺序 不能是0312  走不动才能回头
编辑于 2018-01-30 13:12:44 回复(0)
不懂邻接表!
发表于 2018-01-13 04:54:05 回复(0)
①:0结点入栈
②:0结点出栈,并访问之。  (0)
③:把0结点的邻接结点按1  2   3的顺序入栈
④:栈顶元素3出栈,访问之  (0->3)
⑤:把3结点未访问邻接结点2入栈
⑥:栈顶元素2出栈 ,访问之  (0->3->2)
⑦:把2结点未访问的元素1入栈
⑧:栈顶元素1出栈,访问之 (0->3->2->1)
所以答案是不是错了
发表于 2017-09-07 22:42:07 回复(2)