数据结构与算法 · 单选题 · 第 54 题
计算机基础面试八股 · 第 54 题
在无权图中求两个顶点之间的最短路径(边数最少),最直接、时间复杂度为 O(V+E) 的方法是?
- A深度优先搜索
- B拓扑排序
- CPrim 最小生成树算法
- D广度优先搜索
答案
D D. 广度优先搜索
解析
BFS 按距离一层层向外扩展,第一次到达目标时经过的边数一定最少。DFS 第一次找到的路径不一定最短。拓扑排序只适用于有向无环图且不求最短路;最小生成树求的是连通所有点的最小总权,两点之间的树上路径不一定最短。带非负权重的图用 Dijkstra,有负权边时用 Bellman-Ford。