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

admin2017-04-28 42

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

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

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

拜占庭帝国的发展过程。

下列关于古日耳曼人的社会状况的叙述中，不正确的是()。

巴黎和会讨论的中心问题是()。

中共十四届六中全会《关于加强社会主义精神文明建设若干重要问题的决议》，强调要()。

洋务派创办军事工业的方式是()。

“改土归流”政策的根本目的是()。

下列选项中，不属于列宁《四月提纲》内容的是()。

火的使用，是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。

假定在～个8位字长的计算机中运行如下c程序段：unsignedintx=134;unsignedinty=246；intm=x；intn=y；unsignedintz1=x—y；

从社会学角度来理解社会控制，其内容包括：；；。

Forsomeemployers,thepolicyoflifelongemploymentisparticularlyimportantbecauseitmeansthattheycanputmoneyandeff

下列疾病中哪一种肿瘤最能引起异源性ACTH综合征?()

某企业以划拨方式取得国有土地使用权，现在企业欲将该土地上的房产出租经营，则下列说法正确的是()。

路面设计弯沉值确定时的主要参数是Ne，它是指设计年限内(　　)车道上的累计标准轴次。

水平分析法是将反映企业报告或财务状况的信息与反映企业()财务状况的信息进行对比，研究企业各项经营业绩或财务状况的发展变动情况的一种财务分析方法。

小丽用记号笔把试卷上答错的题目标识出来，便于更高效的复习，这主要运用了知觉的()。

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

计算机408

学硕统考专业

拜占庭帝国的发展过程。

下列关于古日耳曼人的社会状况的叙述中，不正确的是()。

巴黎和会讨论的中心问题是()。

中共十四届六中全会《关于加强社会主义精神文明建设若干重要问题的决议》，强调要()。

洋务派创办军事工业的方式是()。

“改土归流”政策的根本目的是()。

下列选项中，不属于列宁《四月提纲》内容的是()。

火的使用，是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。

假定在～个8位字长的计算机中运行如下c程序段：unsignedintx=134;unsignedinty=246；intm=x；intn=y；unsignedintz1=x—y；

从社会学角度来理解社会控制，其内容包括：________；________；________。

Forsomeemployers,thepolicyoflifelongemploymentisparticularlyimportantbecauseitmeansthattheycanputmoneyandeff

下列疾病中哪一种肿瘤最能引起异源性ACTH综合征?()

某企业以划拨方式取得国有土地使用权，现在企业欲将该土地上的房产出租经营，则下列说法正确的是()。

路面设计弯沉值确定时的主要参数是Ne，它是指设计年限内( )车道上的累计标准轴次。

水平分析法是将反映企业报告或财务状况的信息与反映企业()财务状况的信息进行对比，研究企业各项经营业绩或财务状况的发展变动情况的一种财务分析方法。

小丽用记号笔把试卷上答错的题目标识出来，便于更高效的复习，这主要运用了知觉的()。

从社会学角度来理解社会控制，其内容包括：；；。

路面设计弯沉值确定时的主要参数是Ne，它是指设计年限内(　　)车道上的累计标准轴次。