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

admin2014-04-17 42

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

选项 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

学硕统考专业

第二次世界大战的爆发是多种因素综合作用的结果，其最根本的原因是()。

斯大林模式的突出特点是()。

英国发动鸦片战争的主要目的是()。

波兰三次被瓜分的时间是()

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

1945年8月，毛泽东指出“抗日战争的阶段过去了，新的情况和任务是国内斗争”。此斗争主要集中在()。

试述中国共产党诞生的历史条件和意义。

西南军阀跟随孙中山拥护护法运动的目的是()。

中国共产党召开七届二中全会的主要目的是()。

明末清初，著名学者()抗清失败，前往日本讲学，传播中国文化。

技术性失业又可称为()

七情内伤致病，首先损伤的脏是

下列收入在“营业外收入”账户中核算的内容有()。

入境集装箱须向入境口岸检验检疫机构报检，未经许可不得提运或拆箱。(　　)

下列财务比率公式中正确的有()。

接收“110”报警属于公安领导工作的一种。()

试述运动训练学的主要研究内容。

Peopleareindulginginanillusionwhenevertheyfindthemselvesexplainingatacocktail(鸡尾酒)party，say，thattheare“incompute

Itlookedlikeatypicalbusinessmeeting.Sixmen,neatlydressedinwhiteshirtsandties【C1】________intotheboardroomofas

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

计算机408

学硕统考专业

第二次世界大战的爆发是多种因素综合作用的结果，其最根本的原因是()。

斯大林模式的突出特点是()。

英国发动鸦片战争的主要目的是()。

波兰三次被瓜分的时间是()

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

1945年8月，毛泽东指出“抗日战争的阶段过去了，新的情况和任务是国内斗争”。此斗争主要集中在()。

试述中国共产党诞生的历史条件和意义。

西南军阀跟随孙中山拥护护法运动的目的是()。

中国共产党召开七届二中全会的主要目的是()。

明末清初，著名学者()抗清失败，前往日本讲学，传播中国文化。

技术性失业又可称为()

七情内伤致病，首先损伤的脏是

下列收入在“营业外收入”账户中核算的内容有()。

入境集装箱须向入境口岸检验检疫机构报检，未经许可不得提运或拆箱。( )

下列财务比率公式中正确的有()。

接收“110”报警属于公安领导工作的一种。()

试述运动训练学的主要研究内容。

Peopleareindulginginanillusionwhenevertheyfindthemselvesexplainingatacocktail(鸡尾酒)party，say，thattheare“incompute

Itlookedlikeatypicalbusinessmeeting.Sixmen,neatlydressedinwhiteshirtsandties【C1】________intotheboardroomofas

入境集装箱须向入境口岸检验检疫机构报检，未经许可不得提运或拆箱。(　　)