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

admin2014-04-17 61

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

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

学硕统考专业

继承并发展德谟克利特和伊壁鸠鲁的“原子论”，认为宇宙万物都是由原子构成的，并按照物质本身所特有的规律发展的罗马共和国时期的哲学家()。

我国第一部系统的史学理论著作是()。

汉延熹五年(162)皇甫规得罪宦官，论输左校，太学生()等三百人，跟大官僚一起诣阙陈诉，使皇甫规获得赦免。

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

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

“瓜步之战”发生在下列哪两个政权之间?()

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

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

设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时间为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时问为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。

目前对白血病的MICM分型诊断中，C指的是哪一种分类方法

患者，女，30岁。急性腹痛发作10小时入院，下列哪项检查对诊断急性胰腺炎最有价值

银行业从业人员对客户提出的问题应当本着()的原则答复，不得为达成交易而隐瞒风险或进行虚假或误导性陈述。

西斯蒙第的税收原则在亚当.斯密四原则基础上增加了()。

制定利润分配政策时，应该考虑的投资者的因素是(　　)。

根据政府采购法律制度的规定，下列情形中，采购入可以竞争性谈判方式采购的有()。

根据支付结算法律制度的规定，远期信用汪的付款期限最长不得超过()。

耶基斯一多德森定律表明：动机水平，最有利于激发。

下列对贷款的概念的理解，错误的一项是()。

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

计算机408

学硕统考专业

继承并发展德谟克利特和伊壁鸠鲁的“原子论”，认为宇宙万物都是由原子构成的，并按照物质本身所特有的规律发展的罗马共和国时期的哲学家()。

我国第一部系统的史学理论著作是()。

汉延熹五年(162)皇甫规得罪宦官，论输左校，太学生()等三百人，跟大官僚一起诣阙陈诉，使皇甫规获得赦免。

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

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

“瓜步之战”发生在下列哪两个政权之间?()

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

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

设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时间为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时问为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。

目前对白血病的MICM分型诊断中，C指的是哪一种分类方法

患者，女，30岁。急性腹痛发作10小时入院，下列哪项检查对诊断急性胰腺炎最有价值

银行业从业人员对客户提出的问题应当本着()的原则答复，不得为达成交易而隐瞒风险或进行虚假或误导性陈述。

西斯蒙第的税收原则在亚当.斯密四原则基础上增加了()。

制定利润分配政策时，应该考虑的投资者的因素是( )。

根据政府采购法律制度的规定，下列情形中，采购入可以竞争性谈判方式采购的有()。

根据支付结算法律制度的规定，远期信用汪的付款期限最长不得超过()。

耶基斯一多德森定律表明：动机水平______，最有利于激发______。

下列对贷款的概念的理解，错误的一项是()。

制定利润分配政策时，应该考虑的投资者的因素是(　　)。

耶基斯一多德森定律表明：动机水平，最有利于激发。