首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
admin
2017-04-28
69
问题
下列说法正确的是( )。
Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题
Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量
Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
选项
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://www.kaotiyun.com/show/9JRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
继承并发展德谟克利特和伊壁鸠鲁的“原子论”,认为宇宙万物都是由原子构成的,并按照物质本身所特有的规律发展的罗马共和国时期的哲学家()。
1956年,苏共二十大后,匈牙利大党员和群众强烈要求克服个人崇拜,扩大民主,实行经济改革,一些由知识分子、大学生和干部组成的社团组织纷纷成立,其中最有影响者是()。
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
1905年至1907年间,围绕中国究竟是采用革命手段还是改良方式这个问题,革命派与改良派进行论战的舆论阵地是()。
1956年,毛泽东提出调动一切积极因素为社会主义事业服务这一基本方针的著作是()。
阅读下列史料,并回答问题:在琶勒尼斯(注:地名)一役获胜后,他(庇西特拉图)便占领政府,并解除人民武装;现在他已能稳定地握住僭主政权,并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的:他在塞修斯庙举行了一个武装的阅兵式,同时举行一次民
世界近代史上,世界经济发展经历了两次大的飞跃,即第一次工业革命和第二次工业革命。阅读下面两段材料,回答问题:材料一工业革命的主角——蒸汽机,是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产,主要依靠以人力和经
中书省取代尚书省参与决策的部分职权,使尚书台成为主要行政中枢,这一历史现象出现在()。
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
著名的网络OSI七层模型是由()组织提出来的。
随机试题
中碳钢调质处理后,可获得良好的综合力学性能,其中()钢应用最广。
A.未闭的鞘状突为一条细小管道B.鞘状突下段闭锁而上段未闭C.鞘状突两段闭锁而中段不闭D.右侧睾丸下降迟于左侧E.腹内斜肌弓状下缘发育不全或位置偏高右侧腹股沟疝多见的原因是
关于卵巢的功能,下述何项是错误的()
被代理人死亡后有下列哪些情况之一的,委托代理人实施的代理行为有效()。
国有企业土地资产处置管理的工作中心是什么?
竞争性谈判方式,是指要求采购人就有关采购事项,与不少于()家供应商进行谈判。
下列行为中属于操纵市场行为的有()。
学生以情感为纽带自发形成的群体,如同乡会、同学会等,属于()。
A、 B、 C、 D、 C
•Forquestions1-8youwillheareightshortrecordings.•Foreachquestion,markoneletter(A,BorC)forthecorrectans
最新回复
(
0
)