BFS 与 DFS 详解
BFS 和 DFS 是面试中最基础的搜索算法。关键不是背模板，而是理解为什么 BFS 用队列、DFS 用栈，以及各自适合什么场景。
面试考察点
面试官通过这道题想考察：
1. 你是否理解 BFS 和 DFS 的本质区别
2. 你是否能解释为什么用队列/栈
3. 你是否理解各自的应用场景
4. 你是否能处理 BFS/DFS 的变形题
一、BFS - 广度优先搜索
1.1 BFS 的本质（小白解释）
面试官追问："BFS 为什么用队列？"
BFS = 一圈一圈地扩展
想象向湖里扔石头：
○○○○○○○
○○○ ● ○○○ ← 涟漪扩散
○○○ ○○○
○○○○○○○
从中心开始，一圈一圈向外扩散。
怎么实现？
用队列！
队列 = 先进先出
1. 把起点加入队列
2. 取出队首（最先进来的）
3. 把它的邻居加入队列（队尾）
4. 重复...
先加入的邻居会先被访问 → 一圈一圈扩展！
1.2 BFS 在二叉树中的应用
层序遍历 = BFS
1 ← 第1层
/ \
2 3 ← 第2层
/ \ \
4 5 6 ← 第3层
BFS 结果：1 → 2 → 3 → 4 → 5 → 6
关键：在处理当前层时，下一层的节点已经加入队列
所以当队列非空时，处理完当前层的所有节点后，
自然就到了下一层！
二、DFS - 深度优先搜索
2.1 DFS 的本质
面试官追问："DFS 为什么用栈（或者递归）？"
DFS = 一条路走到黑
想象走迷宫：
1. 从路口 A 出发，随便选一条路
2. 走到路口 B，再随便选一条
3. 走到死路！回退到上一个路口
4. 选另一条路
5. 重复...
这不就是"最深走过的点，先回退"？
栈 = 先进后出
用显式栈实现 DFS：
1. 把起点压栈
2. 弹出栈顶
3. 把它的邻居压栈（弹出顺序决定遍历顺序）
4. 重复...
递归就是隐式的栈！递归调用的返回顺序就是栈的弹出顺序。
2.2 递归实现 DFS
def dfs(node):
if node is None:
return
# 处理当前节点
visit(node)
# 递归遍历子树
dfs(node.left)
dfs(node.right)
递归调用栈的变化：
dfs(A)
→ dfs(B) ← 压栈
→ dfs(D) ← 压栈
→ dfs(None) ← 弹栈
处理 D
→ dfs(None) ← 弹栈
处理 B
→ dfs(E) ← 压栈
→ dfs(None)
处理 E
→ dfs(None)
处理 B 完成 ← 弹栈
处理 A 完成 ← 弹栈
三、BFS vs DFS
3.1 核心区别
┌─────────────────────────────────────────────────┐
│ BFS vs DFS │
├─────────────────────────────────────────────────┤
│ │
│ BFS：队列实现，一圈一圈扩展 │
│ - 找最短路径（无权图） │
│ - 层序遍历 │
│ - 空间 = O(最宽层的节点数) │
│ │
│ DFS：栈实现，一条路走到黑 │
│ - 拓扑排序 │
│ - 连通分量 │
│ - 空间 = O(树的深度) │
│ │
└─────────────────────────────────────────────────┘
3.2 什么时候用 BFS？什么时候用 DFS？
用 BFS：
1. 最短路径（无权图）
2. 层序遍历
3. 找所有可达节点
用 DFS：
1. 拓扑排序
2. 检测环
3. 路径搜索
4. 回溯类问题（排列组合）
记忆口诀：
"BFS 找最近，DFS 找全部"
四、面试真题讲解
4.1 二叉树的最大深度
考察点：DFS vs BFS
方法1 - DFS：
def maxDepth(root):
if root is None:
return 0
left_depth = maxDepth(root.left)
right_depth = maxDepth(root.right)
return max(left_depth, right_depth) + 1
方法2 - BFS：
def maxDepth(root):
if not root:
return 0
depth = 0
queue = [root]
while queue:
depth += 1
for _ in range(len(queue)):
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth
4.2 岛屿数量（LeetCode 200）
考察点：BFS/DFS 解决连通分量
问题：二维网格中，'1' 是陆地，'0' 是水。
有多少个岛屿（相连的陆地）？
思路：
遍历每个格子，如果是 '1' 且未访问：
用 BFS/DFS 把这片陆地标记为已访问
岛屿数 + 1
为什么对？
因为 BFS/DFS 能遍历一个连通分量！
五、面试总结
核心要点
BFS = 队列 = 一圈一圈扩展 = 最短路径
DFS = 栈/递归 = 一条路走到黑 = 回溯
BFS 空间取决于最宽层
DFS 空间取决于树/图深度
面试能加分的回答
1. 能解释为什么用队列/栈
"队列先进先出 = BFS 的一圈一圈扩展"
2. 能说清应用场景
"找最短路径用 BFS，拓扑排序用 DFS"
3. 能对比复杂度
"BFS 空间看最宽层，DFS 空间看最大深度"
相关题目
- LeetCode 102 - 二叉树的层序遍历 - BFS
- LeetCode 200 - 岛屿数量 - DFS/BFS