题1
题目
Q:下列关于广度优先算法的说法中, 正确的是 ( ).
I. 当各边的权值相等时, 广度优先算法可以解决单源最短路径问题
II. 当各边的权值不等时, 广度优先算法可用来解决单源最短路径问题
III. 广度优先遍历算法类似于树中的后序遍历算法
IV. 实现图的广度优先算法时, 使用的数据结构是队列
A. I、IV
B. II、III、IV
C. II、IV
D. I、III、IV
分析
A:什么叫做单源最短路？单源是指什么？就是从一个点出发，到其他所有点的最短路径
解
A
广度优先搜索以起始结点为中心, 一层一层地向外层扩展遍历图的顶点, 因此无法考虑到边权值, 只适合求边权值相等的图的单源最短路径。广度优先搜索相当于树的层序遍历, 选项 III 错误。广度优先搜索需要用到队列, 深度优先搜索需要用到栈, 选项 IV 正确。