BFS / DFS题型：怎么识别、怎么讲、怎么练
BFS/DFS 的关键不在遍历语法，而在于判断你是在做穷举、结构识别，还是在找按层扩展的最短答案。
覆盖题量
80+
推荐起手
先判断题目需要按层搜、按深度搜，还是两者都能做。
高频误区
visited 标记太晚，导致队列或递归里有大量重复状态。
什么时候该想到这个模式
下手前的检查清单
真正适合面试表达的解题步骤
先识别图模型，并定义邻居如何生成。
无权最短路优先 BFS，结构搜索优先 DFS。
统一维护 visited，避免重复处理状态。
把答案依赖的附加信息一起带上，例如层数或路径和。
如果图不连通，要考虑多起点遍历。
常见变体
网格遍历
适合岛屿计数、染色和边界扩散问题。
树遍历
适合父子层级和路径信息重要的题目。
状态图搜索
适合每个节点都是状态的问题，例如单词接龙或转盘锁。
模板预览
from collections import deque
def bfs(start):
queue = deque([start])
visited = {start}
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in visited:
visited.add(nxt)
queue.append(nxt)
def dfs(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs(nxt)
更像真实刷题路径的推荐题单
这组题不是随机罗列，而是按“先建立识别感，再补关键变体，最后上强度”去排，适合真的拿来做一轮 pattern 复习。
入门建立直觉
#98 Validate Binary Search Tree
判断一棵二叉树是否为合法 BST。
每个子树都会从祖先继承一个取值区间，节点必须严格落在该区间内。
入门建立直觉
#102 Binary Tree Level Order Traversal
返回二叉树的层序遍历结果。
队列中的一层就对应答案中的一层，所以处理当前层前要先固定这一层的节点数。
变体补齐关键状态
#200 Number of Islands
统计网格中的岛屿数量。
只要发现一个陆地格子，就应该一次性把整个连通块都遍历掉。
变体补齐关键状态
#207 Course Schedule
判断在先修课依赖下能否完成所有课程。
只要有向图里存在环，答案就一定是否定的。
高频难点压强练习
#127 Word Ladder
求从 beginWord 到 endWord 的最短转换序列长度。
难点不在 BFS，而在于如何高效生成邻居，避免暴力和所有单词逐个比较。
高频坑点
visited 标记太晚，导致队列或递归里有大量重复状态。
递归 DFS 深度过深，直接爆栈。
把路径相关状态和全局 visited 混在一起。
图不连通时只搜了一个连通块。
练习顺序建议
先刷网格 DFS 和岛屿类问题。
再做树遍历和简单图复制。
然后补拓扑排序和环检测。
最后再做单词接龙这类高难状态图 BFS。