图论算法入门：BFS 和 DFS 不是只差一个队列

图论算法入门：BFS 和 DFS 不是只差一个队列

一、遍历方式决定问题视角

BFS 和 DFS 都能遍历图，但它们适合的问题不同。BFS 一层层扩展，天然适合最短步数、层级关系和扩散过程；DFS 一条路走到底，适合连通性、回溯、拓扑关系和路径探索。不要把它们理解成“队列和栈的区别”这么浅。

刷题时，先问问题需要什么：最短路径还是枚举路径？需要层数还是需要深度？需要访问一次还是需要回溯撤销？答案会决定用 BFS 还是 DFS。

二、选择链路：看目标再选遍历

flowchart TD A[图问题] --> B{是否求最短步数} B -->|是| C[BFS] B -->|否| D{是否需要回溯或连通性} D -->|是| E[DFS] D -->|否| F[按题意建模]

如果边权都相同，BFS 第一次到达通常就是最短步数。如果有权重，就要考虑 Dijkstra 或其他算法。不要把 BFS 硬套到带权图上。

三、代码示例：网格最短路 BFS

from collections import deque def shortest_path(grid): m, n = len(grid), len(grid[0]) q = deque([(0, 0, 0)]) seen = {(0, 0)} dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)] while q: x, y, d = q.popleft() if x == m - 1 and y == n - 1: return d for dx, dy in dirs: nx, ny = x + dx, y + dy if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0 and (nx, ny) not in seen: seen.add((nx, ny)) q.append((nx, ny, d + 1)) return -1

这里seen入队时就标记，避免同一个点重复入队。很多 BFS 超时，不是思路错，而是标记时机错。

四、工程边界：建图比遍历更容易错

图论题常常难在建图。字符串转换、课程依赖、岛屿网格、社交关系，本质都是图，但节点和边要自己抽象。建错图，遍历再熟也没用。写题解时要明确节点是什么，边表示什么，是否有向，是否有权。

取舍方面，邻接表适合稀疏图，邻接矩阵适合稠密图或快速判断边是否存在。复杂度也要跟着结构说清楚。V是点数，E是边数，BFS/DFS 通常是 O(V+E)，但网格题可以写成 O(mn)。

递归 DFS 还要注意栈深。Python 遇到大图可能递归爆栈，必要时改成显式栈。算法题里能 AC 的写法，放到工程里不一定稳。边界意识要从刷题时就培养。

图论题还要警惕重复访问。无向图 DFS 时，如果只判断当前节点，没处理父节点，很容易在两点之间来回递归；BFS 如果出队时才标记，可能同一个节点被多次入队，复杂度直接膨胀。访问标记的时机，是图论代码的基本功。

对于拓扑排序，要区分 BFS 版 Kahn 算法和 DFS 版后序。Kahn 算法能更直观看到入度变化，也更容易判断是否有环；DFS 版写起来短，但状态标记要分未访问、访问中、已完成。题解里说清这个区别，读者更不容易混。

五、总结

BFS 和 DFS 不只是队列和栈的区别。BFS 适合层级和最短步数，DFS 适合连通性和路径探索。图论题先建模，再选遍历，最后讲清复杂度和边界。