1.7 深度优先搜索

上一篇的 BFS 一圈一圈往外扩，这一篇的深度优先搜索（DFS）走的是另一条路：认准一个方向，一条路走到黑，走不通了再退回来换条路。 它俩是图遍历的两大基本姿态，理解了它们，你就掌握了所有图搜索的内核。

1.DFS 的直觉：走迷宫

想象你在走迷宫。你不会先把所有岔路口的第一步都试一遍（那是 BFS），而是挑一条路一直走，走到死胡同或者走过的路，就退回上一个岔口，换条没走过的路继续。一直这样，直到把所有能走的路都走遍。

这就是深度优先（Depth-First）：先深后广，沿着一条路扎到底。"走不通退回来"这个动作叫回溯（backtracking），它是 DFS 的灵魂。

DFS 最自然的实现是递归（递归调用栈天然就是"走到底再退回"）：

DFS(G)
    for each vertex u in G:
        u.color = WHITE, u.parent = NIL
    time = 0
    for each vertex u in G:
        if u.color == WHITE:
            DFS-VISIT(u)

DFS-VISIT(u)
    u.color = GRAY        // 正在访问
    time = time + 1; u.discover = time
    for each neighbor v of u:
        if v.color == WHITE:
            v.parent = u
            DFS-VISIT(v)   // 递归往深处走
    u.color = BLACK        // 访问完，回溯
    time = time + 1; u.finish = time

注意那两个时间戳 discover（发现时刻）和 finish（完成时刻）。它们是 DFS 区别于 BFS 的一个独特产物，后面会看到它们大有用处。

2.BFS 用队列，DFS 用栈

上一篇强调过：BFS 的标志是队列（先进先出）。DFS 的标志是栈——递归调用栈本身就是栈（后进先出）。你刚发现的邻居会立刻被递归处理，而不是排队等同一层的处理完。这就是"一条路走到底"的来源。

所以同一个"从起点出发访问所有能到的点"的任务，BFS 和 DFS 的差别只在用什么数据结构管理"待访问"的节点：队列给你层序，栈给你深度优先。这个对应关系记牢，两种搜索你就都拿下了。

（DFS 也可以不用递归，自己显式维护一个栈来写，逻辑一样。递归只是把"栈"这个数据结构隐藏在了调用栈里。）

3.DFS 的复杂度

和 BFS 一样，DFS 每个顶点访问一次、每条边检查一次（有向图一次、无向图两次），复杂度 $O(V+E)$。线性于图的大小，很高效。

它的空间优势正是相对 BFS 的卖点：递归深度最多是图的最长路径长度，所以空间是 $O(V)$（确切说是 $O(\text{最长简单路径})$），不像 BFS 在宽图上要 $O(b^d)$。图又深又窄时，DFS 远比 BFS 省内存。

4.DFS 的独特本事：发现结构

BFS 擅长找最短路径，DFS 擅长发现图的深层结构。这主要归功于那两个时间戳和回溯的特性。几个经典应用：

连通分量 / 环检测。 对每个没访问过的点启动 DFS，一次启动能走到的所有点就是一个连通分量。检测有向图有没有环，靠的是"递归栈里遇到了 GRAY 节点"——GRAY 表示"正在这条路径上访问"，再撞到它就是有环。

拓扑排序（第五卷 5.1 详讲）。 对一个 DAG（有向无环图）做 DFS，按节点的 finish 时间从大到小排，就得到一个拓扑序。为什么？一个节点 finish 得越晚，说明它在依赖链上越靠前。这个"按完成时间逆序"的招数是 DFS 的招牌。

两类边的发现。 DFS 在遍历时能把图的边分成几类：树边（构成 DFS 树）、回边（指向祖先，揭示环）、前向边、交叉边。这种结构化的分类，BFS 给不了，是 DFS 独有的视角。

5.BFS vs DFS：怎么选

把两者摆一起，选型很清楚：

	BFS	DFS
数据结构	队列	栈（递归）
找最短路径（无权）	✓ 保证最短	✗ 不保证
内存	$O(b^d)$，宽图爆炸	$O(V)$，省
擅长	最短路径、层信息	结构发现、拓扑排序、环检测
找到目标就停	可能要扫很多层	可能很快深入到目标

一句话：要最短、要层的，用 BFS；要省内存、要挖掘结构、目标藏得深的，用 DFS。 后面第五卷的图算法，绝大多数都是在这两种遍历上搭建的。

6.练习

Q1. 为什么说"DFS 用栈、BFS 用队列"？如果把 BFS 的队列换成栈，会得到什么？

BFS 把新发现节点入队、从队头取，先进先出保证了"同层先处理"。DFS 把新发现节点压栈、从栈顶取，后进先出导致"刚发现的立刻被处理"，于是沿一条路走到底。把 BFS 的队列换成栈，先进先出变后进先出，层序就破坏了，行为退化成 DFS。这正说明数据结构的选择决定了搜索的姿态。

Q2. DFS 给每个节点记了 discover 和 finish 两个时间戳。拓扑排序是怎么用 finish 时间得到的？

对 DAG 做 DFS，把所有节点按 finish 时间从大到小排列，就是一个合法的拓扑序。直觉：一个节点 finish 得越晚，说明它处在依赖链越靠前的位置（它依赖的后继都先 finish 了）。这个"完成时间逆序"的技巧是 DFS 拓扑排序的核心，第五卷 5.1 会严格证明。

Q3.（思考题） 同样是遍历图，为什么找最短路径要用 BFS 而不是 DFS？

BFS 按距离层层扩展，第一次到达某点必是最短，所以天然给出最短路径。DFS 一条路走到底，第一次到达某点走的可能是条很绕的远路，不保证最短。所以"求最少步数/最短路径"几乎总是 BFS 的活（无权图）；DFS 的强项在结构发现（环、拓扑、连通性），不在最短路径。

7.小结

深度优先搜索用栈（递归）一条路走到底、走不通回溯，在 $O(V+E)$ 内遍历图、$O(V)$ 空间。它不保证最短路径，但擅长挖掘图的深层结构——环检测、拓扑排序、边的分类都靠它。BFS 和 DFS 是图遍历的阴阳两面，掌握它们，第五卷的所有图算法就有了根基。下一篇我们暂时离开具体算法，补一块贯穿全课的"分析语言"——渐近复杂度分析。