校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 图的遍历
题目

一个无向图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
0 0
卡卡卡

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

发表于 2021-11-02 21:00:00
0 0
寒武紀三葉草

准备三刷这节课!

发表于 2021-09-09 12:50:00
0 0
一零计划

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

发表于 2018-10-13 11:08:14
0 0
小洁癖

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

发表于 2018-10-13 11:08:03
0 0
落地98K

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

发表于 2018-10-13 11:07:52
0 0
碧海问舟

没注意是无向图,,,,

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