图论算法入门：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 硬套到带权图上。三、代码示例网格最短路 BFSfrom 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(VE)但网格题可以写成 O(mn)。递归 DFS 还要注意栈深。Python 遇到大图可能递归爆栈必要时改成显式栈。算法题里能 AC 的写法放到工程里不一定稳。边界意识要从刷题时就培养。图论题还要警惕重复访问。无向图 DFS 时如果只判断当前节点没处理父节点很容易在两点之间来回递归BFS 如果出队时才标记可能同一个节点被多次入队复杂度直接膨胀。访问标记的时机是图论代码的基本功。对于拓扑排序要区分 BFS 版 Kahn 算法和 DFS 版后序。Kahn 算法能更直观看到入度变化也更容易判断是否有环DFS 版写起来短但状态标记要分未访问、访问中、已完成。题解里说清这个区别读者更不容易混。五、总结BFS 和 DFS 不只是队列和栈的区别。BFS 适合层级和最短步数DFS 适合连通性和路径探索。图论题先建模再选遍历最后讲清复杂度和边界。