算法概念速查
BFS 和 DFS 的区别是什么？一张对照表讲清怎么选
一句话定义
DFS（深度优先搜索）一条路走到黑、走不通再回头换路，靠递归或显式栈实现；BFS（广度优先搜索）从起点一圈一圈向外扩散，靠队列实现。最关键的分工只有一句：无权图求「最短步数」必须用 BFS——它第一次碰到终点时走过的层数就是最短距离；而枚举所有方案、探索连通块，DFS 写起来更短更顺手。
先打个比方
在一栋楼里找钥匙：DFS 是钻进第一个房间，翻完里面每个抽屉、柜子再退出来换下一间——路径可以很深，但同时只记着「我这条路怎么走来的」；BFS 是先把离大门最近的一圈房间全部扫一遍，没有再扫第二圈——离门越近越先被翻到，所以第一次找到钥匙时，你走的一定是最短路线。
它是怎么运作的
为什么 BFS 天然求最短路？队列保证节点按「距起点的层数」从小到大出队：第 k 层的所有点处理完才轮到第 k+1 层。于是第一次到达终点时的层数就是最短步数。DFS 第一次到达终点走的只是「碰巧先探到的路」，不保证最短——拿 DFS 求最短步数是高频错误。
空间形状正好相反：BFS 要装下「一整圈」节点，图很宽时队列很大；DFS 只存一条路径加分支现场，图很深时递归栈很深——超大网格用递归 DFS 可能爆栈，此时改显式栈或换 BFS。
两者的骨架高度对称：把 BFS 代码里的队列换成栈，就变成了 DFS 的迭代版。真正决定行为的不是代码长相，而是「下一个处理谁」：队列选最早发现的（先进先出），栈选最晚发现的（后进先出）。
什么时候用：识别信号
题目里出现下面任何一条，就该想到这对工具。
- 求「最短步数 / 最少操作次数 / 最少几轮扩散」→ BFS，别犹豫
- 求「所有路径 / 所有方案」或配合撤销做枚举 → DFS（回溯）
- 数连通块、洪水填充（岛屿数量、图像渲染）→ 两者都行，DFS 代码更短
- 按层处理：层序遍历、每层取值、多源同时扩散（腐烂的橘子）→ BFS 天然分层
- 需要子树信息自底向上汇总（树形问题的后序）→ DFS
别和它们搞混
vs 数据结构之别
DFS 用栈（通常是递归的调用栈），BFS 用队列。栈让你「顺着最新线索深挖」，队列让你「按发现顺序雨露均沾」。
vs 最短路之别
无权图最短路是 BFS 的专利：第一次到达即最短。DFS 第一次到达不保证最短，要遍历完所有路径取最小才行，代价是指数级。边带权重时两者都不够，升级 Dijkstra。
vs 空间之别
BFS 的队列峰值 = 最宽一层的节点数，宽图吃内存；DFS 的栈深 = 最长一条路径，深图（或大网格递归）有爆栈风险。选择时看图是「宽」还是「深」。
配套动画题：眼见为实
每道题都有逐步交互动画，看着数据动起来，比读十遍文字都快。
常见追问
什么时候 DFS 会栈溢出？怎么办？
网格或图非常大、且连通块很深时，递归深度可达几十万层，直接爆栈。两条出路：把递归改成显式栈的迭代 DFS，或者干脆换 BFS——队列不吃调用栈。
边带权重的最短路还能用 BFS 吗？
不能。BFS 的「第一次到达即最短」依赖每步代价相同；边权不等时要用 Dijkstra（非负权）或 Bellman-Ford（含负权）。特例：边权只有 0 和 1 时可用双端队列 BFS。
连通块问题到底选哪个？
静态数一次连通块，DFS 三五行最省事；担心爆栈用 BFS；如果边是动态加入、连通性查询穿插其中，两个都不合适，换并查集。