BFS 和 DFS 各适用什么场景？
算法工程师第 8 / 15 题答题框架
参考思路：BFS(最短路/层序/状态扩散)→DFS(路径/连通性/回溯剪枝)→复杂度与队列栈空间对比→网格与图问题举例。
五个经典回答示范
回答一 · 思路口述版
「BFS 按层扩散用队列，适合求最短路径、最少步数——每步代价相同保证第一次到达即最优；DFS 一条路走到底用递归或栈，适合路径枚举、连通性判断、回溯剪枝。网格类问题两者都能做，选型看目标：数最短距离用 BFS，数方案总数或找任意一条路径用 DFS。」
回答二 · 标准写法
BFS 模板：队列加 visited，入队时立即标记防重复入队，层间用 size 快照。DFS 模板：递归函数处理当前格，标记访问，向四方向递归，回溯类问题要撤销标记。网格坐标越界判断写在递归入口。两个模板我都会在面试白板上直接写熟，并说明 visited 在入队时标记而非出队时——否则队列可能膨胀。
回答三 · 进阶变体
双向 BFS：起点终点同时扩散，搜索空间从 b^d 降到 b^(d/2)；优先队列 BFS（Dijkstra）：步长不等时的最短路；DFS 记忆化：重叠子问题场景把指数复杂度压到多项式——记忆化搜索本质是 DP 的另一种写法；拓扑排序用 BFS（入度表）判环与排序。这些变体按场景准备一两句适用条件即可。
回答四 · 边界与测试
必测：起点即终点、不可达返回约定值、单行单列网格、全障碍、大网格性能（避免重复访问）。常见坑：方向数组写错、坐标行列混淆、斜向移动的条件判断。BFS 求最短路别忘验证无解分支返回 -1。
回答五 · 常见错误
错误一：出队时才标记 visited——队列里同一节点多份，超时。错误二：DFS 忘撤销标记——回溯类题全局污染。错误三：把 DFS 当最短路用——第一次到达不一定最短。点评：图论题的翻车大多是模板细节而不是思路，模板必须写到肌肉记忆。
怎么练这道题
- 打开 模拟练习，选择「算法工程师」方向，限时 3 分钟作答本题。
- 对照上方答题框架，逐点检查：哪些要素没覆盖、哪里表达啰嗦。
- 用自己项目的真实经历替换框架中的占位内容，重讲一遍并录音回听。
这类题在真实面试中常被追问细节，
建议进入限时模式练一遍。