BFS 与 DFS 的区别、原理与应用场景
哪些公司问过
答案要点
- DFS 一条路走到底再回溯,用递归或栈;BFS 按层扩展,用队列
- 两者时间复杂度均为 O(V+E)(邻接表),都需要访问标记
- BFS 适合无权图最短路径、层序遍历、最少步数问题
- DFS 适合回溯枚举、连通分量、环检测、拓扑排序
- BFS 宽图时队列占用大,DFS 递归过深可能栈溢出,可改显式栈
易错点
- BFS 出队时才标记访问,导致同一节点多次入队
- 以为 DFS 也能直接求无权图最短路
- 递归 DFS 在大规模数据上栈溢出
面试官常见追问
- 找最短路径用 BFS 还是 DFS?为什么?
- 栈有哪些应用场景?
- 双向 BFS 是什么?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。