首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
admin
2017-04-28
52
问题
下列说法正确的是( )。
Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题
Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量
Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
选项
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
2
)。
(3)对于有n个顶点e条边的图采用邻接表表示时,进行广度优先遍历的时间复杂度是 O(n+e),空间复杂度是O(n)。
(4)对于有n个顶点e条边的图采用邻接矩阵表示时,进行广度优先遍历的时间复杂度是 O(n
2
)。
转载请注明原文地址:https://kaotiyun.com/show/9JRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列内容是武则天独创的是()
1946年5月,中共中央发布的实现“耕者有其田”政策的重要文件是()。
三大战役的先后顺序是()
原始人群是人类最早的社会组织形式,这种社会组织组成的纽带是()。
“改土归流”政策的根本目的是()。
文艺复兴运动兴起的时间是()。
中华人民共和国恢复在联合国合法席位的时间是()。
在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()
列宁在()报告中论证了在俄国实现和平过渡的可能性和必要性。
IP数据报的报文格式如下图所示。在没有选项和填充的情况下,报头长度域的值为()。
随机试题
感染过程中,血液中最先出现的是()
自主神经系统的功能特点是
消毒的含义是
厌氧菌感染伤口换药选用
选择围堰类型时,必须根据当时当地具体条件,主要原则有()。
用经常性预算收入来偿还到期国债的本息,其实质相当于()。
配制黑火药用的原料是火硝、硫磺和木炭。火硝的质量是硫磺和木炭的3倍,硫磺占原料总量的1/10,要配制这种黑火药320千克,需要木炭多少千克?
按表中数据计算可知,1996年该省房地产业增加值为()。
ThankyouforyourinquiryofOctober1st.Wearenowsendingyouourcatalogtogetherwithsomesamplesofthematerialsyoure
【B1】【B10】
最新回复
(
0
)