首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
admin
2017-04-28
32
问题
下列说法正确的是( )。
Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题
Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量
Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
选项
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
学硕统考专业
相关试题推荐
略述晚清政府发展近代工商业的措施。
1916年研究短波无线电通信,为现代远距离无线电通信奠定了基础的发明家是()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
西欧早期资产阶级反封建斗争以反天主教会的方式进行,主要原因是()①天主教会是最有势力的封建主集团②天主教会是封建的精神工具③天主教会日益腐败④近代自然科学的兴起
以下选项不属于希腊城邦的形成方式和途径的是()。
巴黎和会讨论的中心问题是()。
林则徐的反英国侵略的策略思想不包括()。
1940年毛泽东的《新民主主义论》:“而所谓民主主义,现在已不是旧范畴的民主主义,已不是日民主主义,而是新范畴的民主主义,而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是
下列哪两个国家是第二次工业革命的发源地和“中心”?
一台主机申请了一个到www.ab@C@edu.cn的连接,为了获取服务器的IP地址,首先要进行DNS查询,下图为本次查询的过程,请回答如下问题:(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2
随机试题
子宫内膜癌常见的转移途径有()。
每侧肾上腺一般有几支动脉供应
矿业工程施工安全管理的基本要求包括()。
存货与流动资产的比率属于()。
下列哪一项不属于乌镇的东栅景区?()
“五岳”是中国五大名山的总称,即东岳________、南岳衡山、西岳________、北岳恒山、中岳________。
由中国政府出资的《东盟地区论坛成立20周年纪念册》发布仪式在文莱首都斯里巴加湾举行。今年是东盟和中国建立战略伙伴关系()周年。
0,6,24,60,()
信息化可分成产品信息化、企业信息化、产业信息化、国民经济信息化、社会生活信息化等不同层次。目前正在兴起的智慧城市、互联网金融等是()的体现和重要发展方向。
(1)使用一对多表单向导新建一个表单sport_form。要求:使用“国家”为父表并选择“国家名称”字段作为显示字段,“获奖牌情况”为子表并选择“项目名称”和“名次”字段作为显示字段,使用“国家代码”建立表之间的关系,表单样式选择“阴影式”,按钮类型选择“
最新回复
(
0
)