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

admin2014-04-17 67

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

选项 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://www.kaotiyun.com/show/nexi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

1993年，中共十四届三中全会上通过了《中共中央关于解决社会主义市场经济体制若干问题的决定》，其内容不包括()

文艺复兴时期，系统提出了国家主权理论的政治思想家是()。

关于垄断组织的积极作用，不正确的说法是()。

(北魏孝文帝)“初谋南迁，恐众心恋旧，乃示为大举，因以胁定群情，外谋南伐，其实迁也。1日人怀土，多不所愿，内惮南征，无敢言者。于是定都洛阳。”上引材料不能说明的问题是()。

我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说，如炎帝和黄帝两个部落曾战于()，结果黄帝取得了胜利。

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

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

电子计算机的发展经过了四代，①电子数值积分计算机(ENIAC)；②集成电路计算机；③大规模集成电路计算机；④晶体管计算机；⑤人工智能计算机，其先后顺序是()。

新石器时代的房屋建筑根据环境的不同形成了不同的类型，()地区多为干栏式建筑。

序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。

A、B两商品的价格分别表示为PA、PB，设A商品的需求函数QA=500-PA2-PAPB+2PB2，则当PA=10，PB=20时，商品A的需求量对自身价格需求弹性ηAA(ηAA＞0)=________．

下列关于海洋与淡水的法律规制的说法错误的是()

下列啰音中哪种可见于正常人

市场经济作为一种一般性经济运行方式,最重要的基础和条件是()。

英国科技哲学家斯诺在《两种文化》中说过，“我们必须用以反对技术的恶果的唯一武器，还是技术本身。我们没有别的出路。我们无法退人一个根本不存在的没有技术的伊甸园”。这一观点的错误之处在于()

设总体X～N(μ，σ2)，X1，X2，…，Xn＋1为总体X的简单随机样本，记服从的分布·

ItisonlyinrecentyearsthatwehaverecognizedthatAccordingtotheauthor,whichofthefollowingisthemostimportantr

窗体中有命令按钮Commandl，事件过程如下：PublicFunctionf(xAsInteger)AsIntegerDimYAsIntegerx=20y=2f=-x*yEndFun

期货价差套利要同时在相关合约上进行方向相反的交易，即同时建立一个多头头寸和一个空头头寸。()

LudwigvanBeethovenwasoneofthe【B1】composerswhoeverlived.Hethoughtpeoplethatcouldbe【B2】whentheywrotem

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

计算机408

学硕统考专业

1993年，中共十四届三中全会上通过了《中共中央关于解决社会主义市场经济体制若干问题的决定》，其内容不包括()

文艺复兴时期，系统提出了国家主权理论的政治思想家是()。

关于垄断组织的积极作用，不正确的说法是()。

(北魏孝文帝)“初谋南迁，恐众心恋旧，乃示为大举，因以胁定群情，外谋南伐，其实迁也。1日人怀土，多不所愿，内惮南征，无敢言者。于是定都洛阳。”上引材料不能说明的问题是()。

我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说，如炎帝和黄帝两个部落曾战于()，结果黄帝取得了胜利。

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

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

电子计算机的发展经过了四代，①电子数值积分计算机(ENIAC)；②集成电路计算机；③大规模集成电路计算机；④晶体管计算机；⑤人工智能计算机，其先后顺序是()。

新石器时代的房屋建筑根据环境的不同形成了不同的类型，()地区多为干栏式建筑。

序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。

A、B两商品的价格分别表示为PA、PB，设A商品的需求函数QA=500-PA2-PAPB+2PB2，则当PA=10，PB=20时，商品A的需求量对自身价格需求弹性ηAA(ηAA＞0)=________．

下列关于海洋与淡水的法律规制的说法错误的是()

下列啰音中哪种可见于正常人

市场经济作为一种一般性经济运行方式,最重要的基础和条件是()。

英国科技哲学家斯诺在《两种文化》中说过，“我们必须用以反对技术的恶果的唯一武器，还是技术本身。我们没有别的出路。我们无法退人一个根本不存在的没有技术的伊甸园”。这一观点的错误之处在于()

设总体X～N(μ，σ2)，X1，X2，…，Xn＋1为总体X的简单随机样本，记服从的分布·

ItisonlyinrecentyearsthatwehaverecognizedthatAccordingtotheauthor,whichofthefollowingisthemostimportantr

窗体中有命令按钮Commandl，事件过程如下：PublicFunctionf(xAsInteger)AsIntegerDimYAsIntegerx=20y=2f=-x*yEndFun

期货价差套利要同时在相关合约上进行方向相反的交易，即同时建立一个多头头寸和一个空头头寸。()

LudwigvanBeethovenwasoneofthe【B1】______composerswhoeverlived.Hethoughtpeoplethatcouldbe【B2】______whentheywrotem

LudwigvanBeethovenwasoneofthe【B1】composerswhoeverlived.Hethoughtpeoplethatcouldbe【B2】whentheywrotem