题目
广度优先搜索的优点是()。A. 空间复杂度低B. 时间复杂度低C. 能找到最短路径D. 其余选项都是
广度优先搜索的优点是()。
A. 空间复杂度低
B. 时间复杂度低
C. 能找到最短路径
D. 其余选项都是
题目解答
答案
C. 能找到最短路径
解析
广度优先搜索(BFS)是一种图遍历算法,其核心特点是逐层探索所有节点。本题考查BFS的核心优点,需明确以下关键点:
- 最短路径保证:在无权图中,BFS能确保找到从起点到目标节点的最短路径,因为每一层遍历代表当前步数下的所有可能路径。
- 空间复杂度:BFS需存储所有已访问节点和队列,空间复杂度较高。
- 时间复杂度:BFS时间复杂度为$O(V+E)$,在大规模图中可能较高。
选项分析
- 选项A(空间复杂度低):错误。BFS需维护队列和已访问标记,空间消耗较大。
- 选项B(时间复杂度低):错误。BFS时间复杂度在完全图中可能达到$O(V^2)$,并非高效。
- 选项C(能找最短路径):正确。BFS逐层扩展的特性保证了无权图中路径最短。
- 选项D(其余选项都是):错误。因A、B均不成立。