深度优先搜索
复习
- 图：由节点和边组成
- 图的表示：邻接矩阵与邻接表
- 广度优先搜索：一层一层向外扩张
TL;DR
- DFS 沿一条路走到底，再回头
- 它天然对应递归，也可以用栈实现
- DFS 适合探索连通性、找环、拓扑排序
- 它不保证找到最短路径
正文
如果说 BFS 是“水波扩散”，那么深度优先搜索（DFS，Depth-First Search）就是“一条道走到黑”。
走到底，再回头
DFS 的策略是：从起点出发，随便选一个还没访问的邻居，走过去；到了新节点，再继续往下深入，直到走不动了，才回头，换一个还没走过的分支继续。
这个“走到底再退回来”的过程，和栈的行为完全一致——后进先出：最后进入的分支，最先被处理完、最先退回。
也正因如此，DFS 特别适合用递归来写：访问当前节点，然后对它的每个未访问邻居，递归地执行 DFS。递归的调用栈，正好就是“深入与回退”的过程。
它不保证最短
和 BFS 不同，DFS 找到一条路就一头扎进去，不能保证第一次到达就是最短。
比如从起点到目标，DFS 可能先钻进了很长的一条支路，绕了一大圈才到，而旁边明明有一条更短的路它没先走。所以，要最短路径，找 BFS；要快速探遍，找 DFS。
它能做什么
DFS 的强项在于“深入探索”和“回溯”：
- 判断连通性：能不能从一点到另一点
- 找环：沿着路径深入时，若碰到还在当前路径上的节点，就发现了环
- 拓扑排序：给有依赖的任务排序
- 回溯搜索：走一条路试试，不行就退回来换一条（后面的回溯算法就建立在这个思路上）
你会发现，DFS 的价值不只是“遍历图”，更是一种**“试探—回退”的通用模式**。很多搜索问题，本质都是 DFS 的变体。
无论 BFS 还是 DFS，都会维护“已访问”的标记。正是靠着它，我们才能判断图的连通情况、发现环。下一章就专门来看这两件事。
思考题 1
DFS 为什么天然适合用递归实现？
思考题 2
为什么 DFS 不能保证找到最短路径？
小结
知识点
- DFS 沿一条路径走到底再回退
- 它与递归（或栈）天然对应
- DFS 不保证最短路径
- 常用于连通性、找环、拓扑排序与回溯
参考资料
- Wikipedia(zh)：深度优先搜索：沿路径深入再回退的图遍历算法
- Wikipedia(zh)：回溯法：基于试探与回退的搜索方法
思考题答案（仅供参考）
思考题 1
因为 DFS 的“深入与回退”与函数调用栈高度一致：访问当前节点后，对每个未访问的邻居递归调用 DFS，返回时自然就回到了上一层。递归的调用过程本身，就是 DFS 的执行过程。
思考题 2
因为 DFS 一旦选了一条分支就会一直深入到底，不会像 BFS 那样按距离层层扩展。它可能先钻进很长的支路，绕远才到达目标，因此第一次到达并不保证是最短的。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪