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

admin2019-12-10 60

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

选项 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地址是125．45．23．12，它在以太网上的物理地址为2345AB4F67CD，它收到了一个分组，分组中的目的IP地址是125．11．78．10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。

UNIX系统中，输入／输出设备看作是()。

以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条

某二叉树的先序和后序序列正好相反，则该二叉树一定是()。

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

对同一样品进行重复检测，测定值差别越小，说明该检测

检查眼前部病变的投照位置是

A．增生期B．分泌期C．分泌期分泌功能不足D．呈蜕膜改变E．增生过长

对于手术器械、敷料的灭菌、消毒，以下哪种方法最不常用

善治厥阴头痛的药物是

最易引起胎儿畸形的病毒是

下列金融市场类型中，能够为企业提供中长期资金来源的有()。

我国最高审判机关是___________。