首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
admin
2014-04-17
26
问题
下列说法正确的是( )。
Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题
Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量
Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
选项
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
学硕统考专业
相关试题推荐
“瓜步之战”发生在下列哪两个政权之间?()
简要概括基督教的演变。
1993年,中共十四届三中全会上通过了《中共中央关于解决社会主义市场经济体制若干问题的决定》,其内容不包括()
马克思说:巴黎公社“只不过是在特殊条件下的一个城市起义”。其含义是()。
下列战国时期的城市中,同为诸侯国都城和冶铁中心的是()。
西汉时期,张骞第一次出使西域的主要目的是()
设磁盘的扇区大小为4KB,磁盘转速为15000r/min,磁盘平均寻道时间为4ms,最大数据传输速率为40MB/s,磁盘控制器开销时问为1ms,计算读写一个扇区所需平均时间(不考虑I/O请求队列中的等待时间)。
编写一个算法,实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址?(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所分配的地址对TC
随机试题
重视早期教育,认为学前期是接受教育的最佳期,是知识的播种期,如错过机会,则难以弥补的是()
民族精神是一个民族在长期共同生活和社会实践中形成的,为本民族大多数成员所认同的价值取向、思维方式、道德规范、精神气质的总和。在五千多年的发展中,中华民族形成了伟大的民族精神。中华民族精神的核心是
A.G1期B.S期C.G2/M期D.G0期E.G0+G1期对射线最敏感的细胞周期时相是
幼红细胞浆内的蓝色铁颗粒在6个以上,且环核分布,则称为
某施工单位对某公寓楼投标中标,建筑面积为4326㎡,与招标人签订了合同。合同工期330日历天,2005年9月1日开工。协议书合同价格为316万元。在专用条款中约定,价格的调整,执行通用条款有关规定;单价调整,执行《建设工程工程量清单计价规范》,工程量清单的
某企业组织近来质量出现问题,通过使用排列图,找出主要问题后进行了有效解决,后又派专人对质量改进的知识进行了学习,并掌握了许多质量改进有关知识。解决质量问题时,制定对策并取得成效后,为了防止质量问题再发生,必须做到()。
下列属于执法活动的是()。
《周礼》云:“马八尺以上为龙。”《山海经》曰:“马实龙精。”在古人心目中,马具有龙性,奔腾不息的龙马精神更是中华文化积淀中最宝贵的部分。据《尚书》记载,根据黄河龙马背负图纹画出八卦的是:
Whatpartofthemuseumflooded?
VisitorstoBritainmayfindthebestplacetosamplelocalcultureisinatraditionalpub.Ateamofresearchershave(1)______
最新回复
(
0
)