【算法图解】图的遍历：BFS vs DFS

很多图题的第一步不是写代码，而是做选择：

• 我该用 BFS 还是 DFS？

你如果只会说“BFS 用队列，DFS 用栈”，那还不够。

你要能把它讲成“选型逻辑”：

• 目标是什么？
• 约束是什么？
• 图的结构是什么？

这篇文章用一套对比框架把它讲透。

1. 先用一句话区分

• BFS：按层扩散，先近后远
• DFS：一路向深，走到底再回退

对应的数据结构：

• BFS：队列（FIFO）
• DFS：栈/递归（LIFO）

2. 用同一张图对比遍历顺序

假设图是：

const g = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: [],
  F: [],
}

从 A 出发：

• BFS 可能是：A, B, C, D, E, F（按层）
• DFS 可能是：A, B, D, E, C, F（一路到底再回）

注意：邻接表顺序不同，遍历顺序可能不同，但“层 vs 深”的性质不变。

3. 复杂度：二者都是 O(V+E)

• 时间：$O(V+E)$
• 空间：$O(V)$（visited + 队列/栈）

区别在“空间形态”：

• BFS 在宽度大的图上队列可能很大
• DFS 在深度大的图上栈可能很深（递归风险）

4. 三类题的选型口诀

4.1 最短路（无权图）→ BFS

因为 BFS 按层扩散：

• 第一次到达目标时，步数最少

4.2 连通块/可达性 → DFS 或 BFS 都行

例如：

• 岛屿数量
• 是否存在路径

DFS 写起来通常更短。

4.3 枚举路径/组合 → DFS + 回溯

因为你需要：

• 走一条路
• 记录选择
• 走不通撤销选择

这就是回溯。

5. 工程化建议

• 递归 DFS 可能爆栈：图节点很多时用显式栈
• JS 里队列不要用 shift()：用指针或双端队列
• visited 要尽早标记：避免重复入队/入栈

6. 面试回答模板

• BFS 按层扩散，用队列，适合无权最短路径。
• DFS 一路向深，用递归/栈，适合连通块与路径枚举（回溯）。
• 二者复杂度都是 $O(V+E)$，差异在遍历策略与空间形态。

总结

选 BFS/DFS 的关键不是习惯，而是任务：

• 要最短步数 → BFS
• 要枚举方案 → DFS 回溯
• 要遍历/可达 → 都行，选更好写/更不爆栈的