python2024课程-深度遍历与广度遍历

很多人写 Python 写了两三年，列表、字典、函数、类都用得挺顺，一碰到「遍历一棵树」「找最短路径」「走迷宫」这类题就卡住。不是不会写 for 循环，而是不知道该按什么顺序走、什么时候该回头、什么时候该换一条路。深度遍历和广度遍历就是补这块缺口的内容——它们不是两段可以背下来的模板代码，而是两种不同的「探索策略」，选错了，代码能跑但结果不对，或者结果对但效率差一个量级。

先确认自己缺的是哪一块

这篇导读不假设你已经把数据结构学全了。你可以先对号入座：

• 能写出递归函数，但说不清递归调用栈里到底压了什么，遇到「递归深度超限」只会加大限制；
• 用过 deque 或者列表当队列，但没想过为什么广度遍历用列表 pop(0) 会慢；
• 刷题时能看懂别人写的 DFS/BFS 答案，自己从空白文件开始写就无从下手；
• 知道「深度用栈、广度用队列」这句口诀，但碰到图里有环、有重复节点时不知道怎么标记已访问。

如果中了两条以上，这门课的主题正好压在你的短板上。如果一条都没中，可以直接跳过，去看更偏应用的方向。

两种遍历到底在解决什么

深度遍历（DFS）的核心是「一条路走到黑，走不通再退回来」。它天然适合判断连通性、找所有路径、做拓扑排序、检测环。广度遍历（BFS）的核心是「一层一层往外扩」，它天然适合求无权图的最短路径、做层序遍历、找最近的目标节点。

课程会把这两种策略放到同一批例子上对比：同一棵树、同一张图，分别用 DFS 和 BFS 走一遍，看访问顺序差在哪里，看什么条件下必须用其中一种。这种对照比单独讲一个算法更容易记住——你会清楚「什么时候不能用 DFS」和「什么时候 BFS 会爆内存」。

实现层面要迈过的几个坎

理解思路和写出能跑的代码之间还有距离，这门课会具体处理这些：

• 递归版 DFS 和非递归版 DFS 的转换，显式栈里该存节点还是存状态；
• 用 collections.deque 实现 BFS 队列，以及为什么不用 list 模拟；
• visited 集合的时机——入队时标记还是出队时标记，这个细节直接决定代码会不会重复访问甚至死循环；
• 在二维网格（迷宫、岛屿数量这类题）上如何用方向数组统一处理上下左右；
• 递归深度过大时改写成迭代的通用思路。

这些都是实际写代码时会卡住的地方，不是概念问题，是手上功夫问题。

看完应该能回答的问题

检验自己有没有真的补上缺口，不看记住了多少定义，看能不能答出这些：

• 给定一张有环的图，DFS 和 BFS 分别怎么保证不重复访问同一个节点？
• 为什么求无权图最短路径用 BFS 而不是 DFS？换到带权图呢？
• 同样是层序遍历一棵二叉树，用 BFS 和用带深度的 DFS 各有什么代价？
• 递归 DFS 在什么规模的输入下会栈溢出，怎么改成显式栈？
• 如果图是用邻接矩阵而不是邻接表存的，两种遍历的写法要改哪里？

能顺畅答出来，说明这块补上了；答得含糊，就回去把对应的例子重写一遍。遍历算法的价值不在于背下来，而在于遇到陌生结构时能自己判断该用哪种走法、怎么标记、怎么终止。