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

admin2014-04-17 82

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

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

答案A

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

1971年9月美苏英法四国签署()，肯定了西柏林的占领制度，柏林问题得以解决。

第二次世界大战的爆发是多种因素综合作用的结果，其最根本的原因是()。

下列各组条约的时间排列顺序正确的是()①《布列斯特条约》②《色佛尔条约》③《九国公约》④《洛桑条约》

系统阐明社会主义初级阶段理论是在()。

20世纪初出现的法西斯主义实质上也是一种恐怖主义。它与传统的资本主义政治制度的不同主要体现在()。①实行一党专政②抛弃了议会民主制③对外争夺殖民地④强化思想文化的控制

论述15世纪以后美洲作物在中国和欧洲的传播及影响。(2013年统考真题)

评析郑和下西洋的历史条件和意义。

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

世界古代历史上，对东西方文化交流、传播作出突出贡献的是()

以数组Data[m+1]作为循环队列SQ的存储空间，front为头指针，rear为队尾指针，则执行出队操作的语句是()。

A．水蛭、虻虫、三棱、莪术B．黄连、桂枝、党参、山药C．肉桂、附子、枳实、姜黄D．木香、香附、贝母、前胡

妊娠合并巨幼红细胞性贫血的临床表现哪项是错误的：

下列说法不正确的是()。

某施工单位承建某建设工程项目，该项目建设工期很紧，为了保证工程建设的顺利进行，建设单位向施工单位及时提供了原始坐标点、基准线和水准点等测量控制点等资料。施工单位应首先进行复核，然后将复测结果报()审核。

“雾凇”是一种我国北方冬天常见的自然现象，形成“雾凇”的物态变化是()。

科尔伯格道德认知发展阶段理论中“好孩子”处于()

继发性龋形成的原因如下，除外()。

IEEE802.11MAC层具有多种功能，其中分布式协调功能采用的是______协议，用于支持突发式通信。