下列说法正确的是( )。 Ⅰ．当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题 Ⅱ．广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ．广度优先遍历算法类似于树中的后序遍历算法

admin2017-04-28 70

问题下列说法正确的是( )。
Ⅰ．当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题
Ⅱ．广度优先遍历算法可用来求无向图的所有连通分量
Ⅲ．广度优先遍历算法类似于树中的后序遍历算法

选项 A、仅Ⅰ、Ⅱ
B、仅Ⅱ、Ⅲ
C、仅Ⅱ
D、仅Ⅰ、Ⅲ

答案A

解析 Ⅰ：对于无权图，广度优先搜索总是按照距离源点由近到远来遍历图中每个顶点（这里的距离是指当前顶点到源点路径上顶点的个数），如图3—10所示。图中各顶点分布在3个层上，同一层上的顶点距离源点的距离是相同的。广度优先搜索就是沿着从1～3的层次顺序来遍历各个顶点，并在遍历的过程中形成了一棵树，称之为广度优先搜索生成树，树的分支总是连接不同层上的顶点，如图3—10中粗线所连。由源点沿生成树分支到达其余顶点的距离都是最近的（可以用层号来描述其远近）。因此对于无权图，可用广度优先搜索遍历的方法来求最短路径。而对于有权图，当图中各个边的权值相同的时候，就可以类比为无权图（无权图可理解为各边权值为1），因为各边没有了权的大小之分，则同样可以用广度优先搜索遍历的方式来求最短路径，所以Ⅰ正确。

Ⅱ：从图中的一个顶点进行广度优先搜索可以将与这个顶点连通的顶点全部遍历到，也就找到了该顶点所在的连通分量，因此广度优先遍历可以求出无向图的所有连通分量，所以Ⅱ正确。
Ⅲ：广度优先遍历算法应该是类似于树中的层次遍历算法，所以Ⅲ错误。
综上所述，Ⅰ、Ⅱ正确。
补充：分别使用邻接表、邻接矩阵进行广度、深度优先遍历的时间、空间复杂度的总结。
(1)对于有n个顶点e条边的图采用邻接表表示时，进行深度优先遍历的时间复杂度是O(n+e)，空间复杂度是O(n)。
(2)对于有n个顶点e条边的图采用邻接矩阵表示时，进行深度优先遍历的时间复杂度是O(n²)。
(3)对于有n个顶点e条边的图采用邻接表表示时，进行广度优先遍历的时间复杂度是 O(n+e)，空间复杂度是O(n)。
(4)对于有n个顶点e条边的图采用邻接矩阵表示时，进行广度优先遍历的时间复杂度是 O(n²)。

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

下列说法正确的是( )。 Ⅰ．当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题 Ⅱ．广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ．广度优先遍历算法类似于树中的后序遍历算法

计算机408

学硕统考专业

最早以立法形式巩固大化改新成果的法令是()。

1962年1、2月间，中共中央召开的统一思想、总结经验教训、明确工作方向的会议是()。

“我不想变成上帝，或居住在永恒之中，或者把天地抱在怀里，属于人的那种光荣对我就够了。我自己是凡人，我只要求凡人的幸福。”这句话体现的思想是()

西北战场的关键一仗，由此，西北野战军由防御转入进攻，掌握了战争的主动权的战役是()

在阿拉伯()统治时期，阿拉伯军队曾与当时中国的唐朝军队发生冲突。

“钟鸣鼎食”往往用来形容贵族生活。考古发现的青铜乐器“钟”始见于周代遗址，可能存在于()

巴黎和会上，英美主张把原德国在山东的权利转让给日本，华盛顿会议又表示支持中国让日本归还山东的要求，英美态度发生变化的根本原因是()。

在一个采用请求式调页的虚拟存储系统中，存放在外存上的程序代码调入内存的时机是()。

某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int和shorI型长度分别为32位和16位，并且数据按边界对齐存储。某C语言程序段如下：struct{inta：charb：shOrtc：}record：record.a=273：

患者男性，60岁。胸痹反复发作3个月，现胸部刺痛，夜间尤甚，每次发作持续时间大约10分钟，能够自行缓解，多因生气或者劳累后诱发，平时有心慌，舌质紫暗，脉象沉涩，首选方为：

因痰湿内阻而致的头晕，其临床表现是

为提高补偿效果，降低损耗，阻止用户向电网倒送无功，在高压侧无高压负荷时，不得在高压侧装设()电容器装置。

先张法预应力混凝土梁的跨度为9m(计算跨度为8．75m)，截面尺寸和配筋如题图所示。承受的均布恒荷载标准值gk=14．0kN／m，均布活荷载qk=12．0kN／m，混凝土强度等级为C40，预应力钢筋采用热处理钢筋(fptk=1470N／mm2，fpy=10

某档案馆采用二氧化碳气体灭火系统保护，系统带有感烟、感温火灾探测器，并设置有手动报警按钮，则系统至少接收到()后启动防火区内声光警报器。

某企业于2008年2月底取得一张期限为9个月的商业汇票，本金50万元，月利率为8‰，评估基准日为2008年8月31日，则该应收票据的评估值为()。

“没有农村的稳定就没有全国的稳定，没有农民的小康就没有全国人民的小康，没有农业的现代化就没有整个国民经济的现代化。”这主要是因为（）。

直接标价法与间接标价法没有区别。()

Watchdogsaregrowlingatthewebgiants,andsometimesbitingthem.Europeandata-protectionagencieswrotetoGoogle,Microsof