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

admin2017-04-28 57

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

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

在印度独立和巴勒斯坦建国问题上，英国扮演了什么角色?有什么影响?

魏晋南北朝的手工业技术有所进步，下列各项能反映这一特点的是()。①培育出“三熟之稻”②“灌钢”技术的发明③吴培育出八辈之蚕④纸成为最主要的书写材料

关于斯巴达的论述错误的是()。

詹天佑自主设计修建了中国第一条铁路是在()。

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

近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。

原始人群是人类最早的社会组织形式，这种社会组织组成的纽带是()。

洪秀全以宗教手段组织起义，主要利用的是()。

解放军渡江战役中横渡长江的东西两个攻击点是()。

解放军渡江战役中横渡长江的东西两个攻击点是()。

天人相应。四时脉象变化，如《素问·脉要精微论》所说：“冬日在骨”，则可见

男性，40岁。体重92公斤，身高168cm，无“三多一少”症状，其母有糖尿病。该患者治疗应当首先选择下列哪一项

关于保障诉讼参与人的诉讼权利原则，下列哪些选项是正确的?(2016年卷二第65题)

对于同一投资方案，下列说法正确的是()。[2007年真题]

农村信用社经营存款业务需要遵循的首要原则是()。

全式提单是指详细列有承运人和托运人之间的权利、义务等条款的提单。由于条款繁多，所以又称繁式提单。在实际业务中所使用的，大都是这种提单。（）

设A是n阶可逆矩阵，B是把A的第2列的3倍加到第4列上得到的矩阵，则

设f(x)，f’(x)为已知的连续函数，则方程y’+f’(x)y=f(x)f’(x)通解是()．

编译运行以下程序后，关于输出结果的说明正确的是()。　　publicclassConditional{　　publicstaticvoidmain(Stringargs[]){　　intx=2：　　System.out.printl

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

计算机408

学硕统考专业

在印度独立和巴勒斯坦建国问题上，英国扮演了什么角色?有什么影响?

魏晋南北朝的手工业技术有所进步，下列各项能反映这一特点的是()。①培育出“三熟之稻”②“灌钢”技术的发明③吴培育出八辈之蚕④纸成为最主要的书写材料

关于斯巴达的论述错误的是()。

詹天佑自主设计修建了中国第一条铁路是在()。

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

近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。

原始人群是人类最早的社会组织形式，这种社会组织组成的纽带是()。

洪秀全以宗教手段组织起义，主要利用的是()。

解放军渡江战役中横渡长江的东西两个攻击点是()。

解放军渡江战役中横渡长江的东西两个攻击点是()。

天人相应。四时脉象变化，如《素问·脉要精微论》所说：“冬日在骨”，则可见

男性，40岁。体重92公斤，身高168cm，无“三多一少”症状，其母有糖尿病。该患者治疗应当首先选择下列哪一项

关于保障诉讼参与人的诉讼权利原则，下列哪些选项是正确的?(2016年卷二第65题)

对于同一投资方案，下列说法正确的是()。[2007年真题]

农村信用社经营存款业务需要遵循的首要原则是()。

全式提单是指详细列有承运人和托运人之间的权利、义务等条款的提单。由于条款繁多，所以又称繁式提单。在实际业务中所使用的，大都是这种提单。（）

设A是n阶可逆矩阵，B是把A的第2列的3倍加到第4列上得到的矩阵，则

设f(x)，f’(x)为已知的连续函数，则方程y’+f’(x)y=f(x)f’(x)通解是()．

编译运行以下程序后，关于输出结果的说明正确的是()。 publicclassConditional{ publicstaticvoidmain(Stringargs[]){ intx=2： System.out.printl

编译运行以下程序后，关于输出结果的说明正确的是()。　　publicclassConditional{　　publicstaticvoidmain(Stringargs[]){　　intx=2：　　System.out.printl