深度优先搜索

深度优先搜索（DFS）沿一条分支走到底，再退回调用者，尝试下一条分支。它用栈保存返回路径，递归调用栈就是一种实现。使用邻接表时，遍历可达顶点和边需要 O(V + E) 时间。环检测、拓扑排序和连通性分析都以它为基础。

可以把递归栈看成迷宫里的路线记录：路口先选一条路，走不通就沿记录退回上一个路口。退回称为回溯，它和向下搜索同属 DFS。

深度优先搜索如何工作

进入节点时，先标记并记录它；遍历邻居，对未访问的邻居递归；循环结束后返回。每次递归下降最终都有一次返回。栈顶是当前节点，下面的帧是等待子调用结束的祖先。

本课有两种模式，展示的代码随之变化。

• 树模式： 根到每个节点只有一条路径，沿子边遍历不可能重访，因此代码只有记录、递归、返回，没有 visited 集合。
• 图模式： 边可能汇合或形成环。调用入口标记 visited，只对未标记邻居递归。已访问的目标若还在调用栈中，就是指向祖先的回边，证明存在有向环；默认例中，指向已结束节点的两条边是交叉边，两者都跳过。一般有向图中，指向已结束后代的边还可能是前向边，不能把所有已结束目标都归为交叉边。

深度优先搜索逐步演示

默认选择图模式的有环预设，从 0 开始。六个节点的邻接表为 0 → [1, 3]、1 → [2]、2 → [0, 4]、3 → [4, 5]、4 → [5]、5 → [1]。

1. dfs(0) 标记第 1 个节点，栈为 [0]，递归到 1。
2. dfs(1) 标记第 2 个节点，栈为 [0, 1]，递归到 2。
3. dfs(2) 标记第 3 个节点，栈为 [0, 1, 2]。2 → 0 指向栈中祖先，是回边，跳过；然后递归到 4。
4. dfs(4) 标记第 4 个节点，栈为 [0, 1, 2, 4]，递归到 5。
5. dfs(5) 标记第 5 个节点，栈为 [0, 1, 2, 4, 5]，达到最大深度。5 → 1 也是回边，跳过。随后按 5 → 4 → 2 → 1 → 0 返回。
6. 回到 0 的邻居循环，递归到未访问的 3。它是第 6 个节点，栈为 [0, 3]。3 → 4 和 3 → 5 的目标已经结束，属于本例中的交叉边，跳过。3 返回，再由 0 返回，搜索结束。

访问顺序为 0、1、2、4、5、3。四条边经过检查但未递归跟随：两条回边 2 → 0、5 → 1 会闭合环；两条交叉边 3 → 4、3 → 5 只是重复到达已完成区域。区分“仍在栈中”和“已经结束”是这里检测有向环的机制。

其他预设便于单独观察顺序。树模式有平衡树和偏斜树；七节点平衡树为 0 → [1, 2]、1 → [3, 4]、2 → [5, 6]。DFS 顺序是 0, 1, 3, 4, 2, 5, 6，先完成 1 的整棵子树，再进入兄弟节点 2。BFS 则逐层访问：0, 1, 2, 3, 4, 5, 6。图模式的简单预设只有一条交叉边，没有回边，适合观察访问标记的作用。

画布上的焦点环在调用时沿边下降，返回时沿边上升；右侧调用栈同步增减。未到达节点为淡蓝色，栈内节点为橙色，当前节点更深、等待中的祖先更浅，结束节点变绿。跳过回边或交叉边时，该边闪红。

时间与空间复杂度

访问标记保证每个可达顶点只进入一次，每条有向边从起点检查一次。递归栈保存根到当前节点的路径，长链上可达 O(V)；加上访问记录，总空间仍为 O(V)。长链使 DFS 栈变深，而 BFS 队列可以很小；宽层则会使 BFS 队列增大。

边界情况

• 单节点无边：标记后没有邻居，立即返回。
• 不连通图：一次 DFS 只访问从起点可达的部分。无向图中这就是起点所在连通分量；覆盖全图需对每个未访问节点重新开始。
• 存在环：访问标记阻止沿回边再次进入运行中的调用，递归可以结束。
• 很深的链：可能超过运行时递归栈上限，可改用显式栈。

常见错误

1. 图上省略访问检查，环会导致无限递归。只有沿子边遍历的树模式可以省略。
2. 在邻居循环后才标记访问。节点运行期间，环就可能再次进入它；应在调用入口标记。
3. 只看下降，忽略返回。拓扑排序、完成时间、割点等算法会在返回阶段处理信息。
4. 认为只有一个正确顺序。0 → [1, 2] 与 0 → [2, 1] 会产生不同但都有效的 DFS 顺序。
5. 混淆栈和队列。DFS 用后进先出推进深度，BFS 用先进先出推进层次；实现显式栈时也要保持相应的访问标记和邻居处理规则。