试题-一个无向图G=(V,E),顶点集合V={1,2,3,4,5,6,7},边集合E={(1,2), (1,3),(2,4), (3,4), (4

题目

一个无向图G=(V,E),顶点集合V={1,2,3,4,5,6,7},边集合E={(1,2), (1,3),(2,4), (3,4), (4,5),(4,6), (5,7) , (6,7)}，从顶点1出发进行深度优先遍历，可得到的顶点序列是（）

A.1,2,3,4,5,6,7

B.1,2,4,3,6,7,5

C.1,3,4,5,7,6,2

D.1,2,4,6,7,5,3

解答

正确答案是 B C D

首先画出如上所示的图。

从节点1出发有两种选择，要么2要么3。

所谓深度优先遍历是指从一个节点出发，一个走到其中邻居节点，将该邻居节点标记为已遍历，然后从该节点出发，重复上述步骤，知道遇到节点的出度为0或，节点的邻居都已遍历，再返回到最开始出发的节点，找到其未遍历的另一个邻居节点，重复上面的步骤即可。

这个题目容易出错的是，要注意节点4，它有三个邻居节点，分别是3、5、6，因此选项BCD都是正确的答案。但A肯定不是，因为2的邻居存在且不为3。

C 7条回复评论

无畏无所畏

看完解析才知道应该是这样的思路

发表于 2022-01-03 23:00:00

卡卡卡

会计想转行学计算机或者电子信息工程类目前觉得计算机可能就业好一点但是不知道从哪开始学最好？

发表于 2021-11-02 21:00:00

寒武紀三葉草

准备三刷这节课！

发表于 2021-09-09 12:50:00

一零计划

觉得B不是正确答案，求解答。

发表于 2018-10-13 11:08:14

小洁癖

如果使用visited标记，b是对的，如果使用open表和close表，b就不是

发表于 2018-10-13 11:08:03

落地98K

b中到达4没有满足边界条件就回到3，个人感觉不算深度遍历吧

发表于 2018-10-13 11:07:52

碧海问舟

没注意是无向图，，，，

发表于 2018-10-13 11:07:44