下列说法正确的是( )。 Ⅰ．当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题 Ⅱ．广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ．广度优先遍历算法类似于树中的后序遍历算法

admin2014-04-17 83

问题下列说法正确的是( )。
Ⅰ．当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题
Ⅱ．广度优先遍历算法可用来求无向图的所有连通分量
Ⅲ．广度优先遍历算法类似于树中的后序遍历算法

选项 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²)。
(3)对于有n个顶点e条边的图采用邻接表表示时，进行广度优先遍历的时间复杂度是O(n+e)，空间复杂度是O(n)。
(4)对于有n个顶点e条边的图采用邻接矩阵表示时，进行广度优先遍历的时间复杂度是O(n²)。

转载请注明原文地址:https://kaotiyun.com/show/nexi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

下列说法正确的是( )。 Ⅰ．当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题 Ⅱ．广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ．广度优先遍历算法类似于树中的后序遍历算法

计算机408

学硕统考专业

略论中国近现代历史上的“军阀”问题。(北京大学2003年中国通史真题)

汉武帝时，为太常博士的弟子兴建学校，名为()，学生入学后免除本人的徭役，学成经考试后，

反映查理大帝进攻阿拉伯人控制的西班牙的文学作品是()。

《吕氏春秋》载：“公作则迟，有所匿其力也；分地则速，无所匿其力也。”这条材料反映的实质问题是()。

在19世纪60年代到90年代，洋务派兴办洋务事业的主要目的是()。

以下不属于国民党控制金融的“四行”的是()。

现今我国裕固族的祖先是()

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

元朝在中央设置中书省、地方则设置行中书省，其目的是()。

编写一个算法，实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。

A.有头疖B.无头疖C.疖病D.蛇肚疔E.蛇头疔皮肤上有一红色结块，范围约3cm，无脓头，表面灼热，触之疼痛。此为()

搜索引擎结果页面的缩写是______。

对蛛网膜下腔阻滞麻醉(腰麻)术后并发低压性头痛的处理，下列哪项是不恰当的

A、当日B、3日C、5日D、7日E、14日；根据《处方管理办法》处方最长有效期不得超过

如图3-115所示，屋架在外力P作用下，下列关于各杆件的受力状态的描述，哪一项正确?[2006年第7题]Ⅰ．上弦杆受压，下弦杆受拉Ⅱ．上弦杆受拉，下弦杆受压Ⅲ．各杆件均为轴力杆Ⅳ．斜腹杆均为零杆

题24～26：非抗震的某梁柱节点，如图1-5所示。梁柱均选用热轧H型钢截面，梁采用HN500×200×10×16(r=20)，柱采用Hm390×300×10×16(r=24)，梁、柱钢材均采用Q345B。主梁上、下翼缘与柱翼缘为全熔透坡口对接焊缝，采用引弧

存货确认是以法定产权的取得为标志的。具体来说下列哪些项目属于企业的存货范围()。

下列关于复利计息和有效年利率的说法中，错误的有()。

某企业从银行取得借款1000万元(名义借款额)，期限一年，名义利率为6％。要求计算下列几种情况下的实际利率：银行规定补偿性余额比例为8％；