首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
admin
2014-04-17
76
问题
下列说法正确的是( )。
Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题
Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量
Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
选项
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
2
)。
(3)对于有n个顶点e条边的图采用邻接表表示时,进行广度优先遍历的时间复杂度是O(n+e),空间复杂度是O(n)。
(4)对于有n个顶点e条边的图采用邻接矩阵表示时,进行广度优先遍历的时间复杂度是O(n
2
)。
转载请注明原文地址:https://kaotiyun.com/show/nexi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
第二次世界大战的爆发是多种因素综合作用的结果,其最根本的原因是()。
“冷战”局面的形成是由于()①美国试图称霸世界②苏联政治军事力量增强③欧亚社会主义阵营形成④美苏展开核军备竞赛
蒙古军西征之后,罗斯处于()的控制之下。
所罗门死后不久,以色列犹太王国遂分裂为北方的以色列王国和南方的犹太王国。后来,两国分别为哪两个国家所灭?()
北魏建立和统一的时间分别是()。
“时方镇缺守帅,稍命文臣权之……又置转运使、通判,为之条禁,文薄渐为精密,由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。
试述中国共产党诞生的历史条件和意义。
论述15世纪以后美洲作物在中国和欧洲的传播及影响。(2013年统考真题)
评析郑和下西洋的历史条件和意义。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
随机试题
在路径一目标理论中,对下属十分友善,表现出对下属的关怀的是()
下列有关嗜铬细胞瘤的描述正确的是
“郁证全在病者能移情易性”出自哪部医学著作
依据《专利法》的规定,侵犯专利权的,权利人的损失、侵权人获得的利益和专利许可使用费均难以确定的,人民法院可以根据专利权的类型、侵权行为的性质和情节等因素,确定给予()的赔偿。
在下列哪些情形下,人民法院可以裁定驳回起诉?()
产权具有()等基本属性。
我国住房抵押贷款的计息方式是按()计息。
《四库全书》是清朝乾隆帝亲自组织的中国历史上一部规模最大的丛书,该书包括经、史、子、集四部,可谓超级文化大典。《四库全书总目提要》中称其所收录的某人的著述“狂悖乖谬,非圣无法”“排击孔子,别立褒贬”。这里的“某人”是指()。
关系模式R中若没有非主属性,且只有两个属性,则()。
______I’mwillingtohelp,Idonothavetoomuchtimeavailable.
最新回复
(
0
)