一起动脑筋 · 先看一个小故事
找树屋里的旗子，机器人有两种走法：一条路先走到底，或先看完附近所有房间。
把过程摊开来看
- DFS深入，再回退
- BFS近层，再远层
- 记录工具栈与队列
- 按问题选择是否需要最少步数
DFS 与 BFS 的主要区别是探索顺序。
两者都可以检查可达性；无权图的最短路径常用 BFS。DFS 常用于探索分支结构，是否更省空间要看图的形状。
01它们最大的区别是什么？
DFS
先沿一条路尽量走深。
BFS
先把同一距离的一层处理完。
02分别使用什么结构？
DFS
递归调用栈或显式 stack。
BFS
queue 队列。
03谁能找最短路？
在无权图中：
- BFS 可以保证最短边数
- 普通 DFS 找到的第一条路径不保证最短
04谁更省内存？
没有统一答案。
DFS 需要保存当前深度路径及相关状态；BFS 可能需要同时保存一整层甚至很多待处理节点。
05时间复杂度一样吗？
如果使用邻接表，并且每个节点和边只处理常数次，DFS 和 BFS 遍历一般图通常都是：
O(V + E)
V 是顶点数，E 是边数。
06什么时候更适合 DFS？
- 需要深入尝试和回溯
- 树的递归结构
- 连通分量
- 拓扑、桥、割点等很多图算法基础
07什么时候更适合 BFS？
- 无权最短路
- 层序遍历
- 按距离一层层扩散
- 多源最短步数
你已经知道了什么
- DFS 深入优先，BFS 分层优先。
- DFS 常用栈，BFS 常用队列。
- 无权最短步数通常使用 BFS。
- 两者遍历邻接表图通常都是 O(V+E)。
- 内存谁更省取决于具体图和实现。
下一篇：为什么有的程序一秒就完成，有的要跑很久？
轮到你来试一试
目标就在起点隔壁，但 DFS 先选了一条很长的路，会怎样？
想好了吗？点开看解释
可能很晚才回来检查隔壁；BFS 会先检查所有一步可达的位置。