如果从无向图的任意一个顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是( )。

admin2019-12-10 37

问题如果从无向图的任意一个顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是( )。

选项 A、完全图
B、连通图
C、有回路
D、一棵树

答案B

解析图的一次深度优先搜索遍历，可以遍历完图中一个连通分量中所有的顶点。如果图是连通的，则图只含有一个连通分量，即图本身，这样一次深度优先搜索遍历即可遍历完图中所有顶点。因此本题选B。完全图相当于在连通图上加上了更严格的条件，即任意两个顶点间都存在边，对于满足本题的要求不需要完全图，条件达到连通图的强度就足够了。
可能疑问点：有些考生可能认为D也正确，树难道不是连通图吗?
提示：树的类型有很多，相信选D的同学必定是思维定式，总是想着普通的无向树，这些树当然是连通图。但是，是否想过有向树?想必提到这个概念误选D的考生就会恍然大悟了，不再多做解释。
补充：用深度优先算法遍历一个无环有向图，并在深度优先退栈返回时打印相应的顶点，则输出的顶点序列是逆拓扑有序。

转载请注明原文地址:https://kaotiyun.com/show/Wm3i777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

如果从无向图的任意一个顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是( )。

计算机408

学硕统考专业

磁盘机由6个盘片组成，其中专设1个盘面为伺服面，其他的盘面作为记录数据的盘面。盘存储区域内直径为6．1cm，外直径为12．9cm，道密度为220TPM，位密度为6000bpm，平均寻道时间为10ms，磁盘转速为7200RPM。假定7π=3，试计算：

用链接方式存储的队列，在进行删除运算时，下面正确的是()。

下面是给出的一段IP数据包头所包含的数据，0000305252400080062C23C0A80101D803E215，请根据IPv4头部格式回答如下问题：(1)该IP包的发送主机和接收主机的地址分别是什么?

已知一组关键字为(26，36，41，38，44，15，68，12，6，51，25)，用链地址法解决冲突。假设装填因子a=0．75，散列函数的形式为H(K)=KMODP，回答下列问题：(1)构造散列函数；(2)画出散列表；

某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作，则不可能得到的出队序列是____。

已知有6个顶点(顶点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。要求：求图G的关键路径，并计算该关键路径的长度。

已知有6个顶点(顶点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。要求：画出有向带权图G。

1871年子安峻创办的日本第一家日报是()

所有的急性肾小球肾炎的患者均可见

患者，女性，35岁，近4天发热、腰痛，伴尿急、尿频、尿痛，尿镜检示白细胞增多，27／HP。可能的原因是

下列各项中，构成固定资产原值，但是不构成“形成固定资产的费用”的有()。

对文书进行誊抄缮写的工作称为()。

下列不属于县市级以上行政机关政务公开内容的是()。

关系数据模型的三个组成部分中不包括()。

Itis,everyoneagrees,ahugetaskthatthechildperformswhenhelearnstospeak,andthefactthathedoessoinsoshorta

Ayoungmangoingtojointhearmy(军队)andhadto【C1】______amedicalexamination.Thedoctorwassittingatadeskwhenhecamei