图系列第 5 篇：深度优先搜索 DFS

嘿，朋友，欢迎回到图系列。这是第 5 篇，我们要认识图论里另一尊大神——深度优先搜索，英文叫 Depth-First Search，江湖人称 DFS。

第 4 篇我们用了整整一篇的篇幅讲 BFS：队列是它的发动机，visited 是它的安全带，水波一圈一圈往外扩，最短步数问题被它轻松拿下。今天的主角换成了 DFS，气质截然不同：BFS 像个稳重的外交官，先把身边的熟人全部拜访一遍，再慢慢向外拓展；DFS 则像个执着的探险家，选定一条路就一直走到黑，走不动了才回头，回头之后还要再找下一条没走过的路继续钻。

这一篇会把这些东西讲透：先建立”一路走到黑再回头”的直观；然后给出递归实现，重点讨论 visited 的标记时机；接着拿一张具体的图完整手算走查一遍，把递归调用栈的变化一帧一帧画出来；再用显式栈写一个迭代版，看看它和递归版在访问顺序上有什么微妙差异；随后引出 DFS 树和时间戳这两个强大的分析工具，顺手认识前向边、回边、横叉边；之后预览 DFS 的四个招牌应用——连通分量、环检测、拓扑排序、强连通分量；再把 DFS 和 BFS 放在同一张桌子上全面对比；最后用岛屿数量、迷宫路径两个典型问题收尾，附上速查表和自测题。

如果你读过树系列的第 5 篇（树的 DFS 遍历），你会发现今天的很多招式似曾相识：前序、中序、后序，递归、栈，都是一路传下来的老手艺。但图比树多了一个巨大的麻烦——环。树里你永远不会走回祖先，图里却随时可能一脚踩回老路。所以今天我们反复强调的核心问题只有一个：怎么保证遍历不会原地转圈？答案就是 visited。

把 BFS 和 DFS 并排放在一起看，两者的性格差异一目了然：

flowchart LR
    subgraph B["BFS：先扫完眼前这一圈"]
        direction LR
        B1["队列"] --> B2["一层一层扩散"]
        B2 --> B3["关心距离"]
    end
    subgraph D["DFS：先钻进最深的角落"]
        direction LR
        D1["栈"] --> D2["一条路走到黑"]
        D2 --> D3["关心结构"]
    end

这个对比会在第 7 节全面展开，现在先在心里种下一颗种子：队列管广度，栈管深度。本篇后面所有内容，都是这颗种子长出的树。

为了让本篇自洽，先把需要用到的旧知识快速对齐一遍：

• 图的存储（第 3 篇）：邻接表里，graph[u] 是顶点 u 的邻居列表；本文所有代码默认邻接表。
• BFS 的教训（第 4 篇）：遍历必须用 visited 防重复；BFS 用队列按层扩散，DFS 用栈按深钻探。
• 树的 DFS（树系列第 5 篇）：前序遍历、后序遍历、递归与回溯；树上不需要 visited，图上必须加。
• 连通分量（第 2 篇）：无向图中互相可达的顶点构成一个连通块，DFS 可以数出连通块个数。

如果这些概念还有模糊，建议先回去翻对应篇章，再来读本篇会顺畅很多。下面这张表是四篇内容的”依赖关系图”：

graph LR
    S1["第 1 篇：图的基本概念"] --> S3["第 3 篇：邻接表/邻接矩阵"]
    S3 --> S4["第 4 篇：BFS（队列 + visited）"]
    S3 --> S5["本篇：DFS（栈 + visited）"]
    S2["第 2 篇：连通性"] --> S5
    T5["树系列第 5 篇：树的 DFS"] --> S5
    S5 --> S6["第 6 篇：BFS/DFS 的应用"]

好，收拾行囊，我们出发。

1 直观：一条路走到黑，走不动就回头

1.1 迷宫的直觉

想象你走进一座没有地图的迷宫，手里只有一支粉笔。你的策略非常简单：看见岔路口就随便选一条走进去；在走过的地面上画一道粉笔记号；如果走到死胡同，或者发现前面的路已经画过记号，就原路退回到上一个岔路口，换一条没走过的路继续。这就是 DFS，只不过迷宫换成了图，岔路口换成了顶点的邻居列表。

和 BFS 的”水波式扩散”相比，DFS 更像一只蚂蚁在迷宫里留下的探索轨迹：它不追求”同时到达”，而是以深度为第一优先级。只要前方还有没走过的路，就绝不回头；只有当所有能走的方向都走过了，才退回来，这就是”深度优先”四个字的含义。

下面这张图用一个五层的小迷宫来展示 DFS 的轨迹。起点是 S，目标藏在 H，箭头标出探索的方向：

graph LR
    S["S（起点）"]
    A["A"]
    B["B"]
    C["C"]
    D["D"]
    E["E"]
    F["F"]
    G["G"]
    H["H（目标）"]
    S --> A
    A --> B
    B --> C
    C --> D
    D --> E
    E --> F
    F --> G
    G --> H

这条路 S → A → B → C → D → E → F → G → H 一气呵成，中间没有回头，因为每一步都还有新的路可走。但真实的图通常有岔路：假设在 C 这个路口，除了通向 D，还有一条通往 M 的岔路，DFS 会先钻进 M，把 M 那条支线全部走完、彻底死心之后，才退回到 C，再走向 D。下面的流程图描述了这个”钻进去—走到黑—退回来—换路”的循环：

flowchart TD
    Start["从当前顶点出发"] --> Check["存在未访问的邻居？"]
    Check -- "有" --> Go["选一个未访问邻居，走进去"]
    Go --> Start
    Check -- "没有" --> Back["所有邻居都已访问，返回上一顶点"]
    Back --> Prev["上一顶点继续寻找其他未访问邻居"]
    Prev --> Check

注意流程图里的”返回”：DFS 不是走完一条路就结束，而是要一层一层退回去，把沿途每个顶点剩余的分支全部扫干净。这个”退回去”的动作在递归里天然存在——函数调用结束，控制权就交还给上一层调用者；在显式栈版本里，它就是出栈。

1.2 与树的 DFS 一脉相承

树系列的读者还记得，二叉树有三种经典遍历：前序（根 → 左 → 右）、中序（左 → 根 → 右）、后序（左 → 右 → 根）。它们都是 DFS：沿着一条分支一路深入，走到底再回头。树的 DFS 长这样：

graph TD
    R["根"]
    L["左子树"]
    Rt["右子树"]
    R --> L
    R --> Rt

对一棵树做 DFS，从根出发，先钻进左子树，把左子树整棵遍历完，再回到根，钻进右子树。这个过程不需要 visited，因为树没有环，每个节点只会被它的父亲访问到一次，天然不会重复。

图上的 DFS 几乎一模一样，唯一的区别就是要多带一支”粉笔”：每走进一个顶点，就在名单上记一笔，以后任何路径再看到它，都当成”走过”绕开。为什么会这样？因为图里有环。请看下面这张无向图，如果 DFS 从 A 出发，沿着 A → B → C → D 走到 D，D 的邻居里有一个 C——C 已经访问过了。没有 visited 的话，DFS 会从 D 再钻进 C，又从 C 钻回 B，从 B 钻回 A，再从 A 钻回 D……永远在环上转圈，递归栈无限增长，最终栈溢出。

graph LR
    A["A"] --- B["B"]
    B --- C["C"]
    C --- D["D"]
    D --- A

所以一句话总结图和树的 DFS 的关系：图上的 DFS = 树上的 DFS + visited。树靠结构保证不重复，图必须靠显式的标记来保证。

1.3 visited 的两层作用

visited 在 DFS 里做两件事。第一件事是防止死循环：有了它，环上走过的顶点不会再被重复进入，遍历必然终止。第二件事是保证每个顶点最多被”探索”一次：DFS 的复杂度之所以能控制在 O(V + E)，正是因为每个顶点只进入一次、每条边只被检查有限的次数；没有 visited，同一个顶点可能被重复进入无数次，复杂度就没边了。

在无向图里，visited 还有一个很形象的副产品：DFS 走过的边恰好构成一棵树（或一片森林），这棵树被叫作 DFS 树。环上那些没被走到的边，则被叫作”回边”——它们像一条秘密通道，把后代直接连回祖先。这个概念第 5 节会详细展开。

1.4 动手体验

光看文字还是隔了一层。强烈建议你现在打开下面的可视化实验室，自己建一张带环的图，选好起点，点一下”DFS”，亲眼看蚂蚁是怎么钻进去又退出来的。看完动画再回来读后面的手算走查，会顺畅得多：

好，直观先到这里。接下来我们把”蚂蚁钻迷宫”翻译成代码。

1.5 三个生活比喻，帮你把 DFS 钉进记忆

除了迷宫探险，DFS 还有几个流传很广的生活比喻，每个都抓住它的一个侧面：

比喻一：翻阅一本超厚的百科书。你从目录第一个词条开始，发现词条里有”参见 XX”，就立刻翻到 XX 那一页；XX 里又提到 YY，再翻过去……直到某个词条没有任何”参见”，你才回到上一页，继续读剩下的部分。这个过程和 DFS 一模一样：链接就是边，参见就是邻居，“翻到最深处再回来”就是回溯。

比喻二：清理一串嵌套的括号。表达式 ((a+b)*(c-d)) 里，最内层的括号最先被处理，然后一层层向外。DFS 的完成顺序也是从最深的内层开始向外——这正是第 5 节括号序列的由来。

比喻三：深度清理抽屉。你整理衣柜，拉开最上面一格，发现里面有个小盒子，你打开小盒子，盒子里又有个小袋子，你翻遍小袋子才回来继续整理抽屉。整理这件事”陷得越深越先完成”，和 DFS 的后序位置完美对应。

这三个比喻的共同点是：新任务永远优先于手头的旧任务，旧任务只是被”暂停”而不是被”放弃”。暂停后还能恢复，靠的是栈——无论是递归调用栈还是显式栈。记住”暂停-恢复”这四个字，DFS 的一切行为都能从这个模型推导出来。

2 递归实现：代码最少，思路最直接

2.1 伪代码

DFS 的递归版本是所有版本里最短的，核心只有三句话：

function dfs(顶点 u):
    如果 u 已访问: 返回
    标记 u 已访问
    输出 u  // 前序位置：刚进入 u 时做点什么
    对于 u 的每个邻居 v:
        dfs(v)
    输出 u  // 后序位置：u 的所有邻居都探索完，准备返回

整个函数干的事情是：进入一个顶点，先给自己盖章（标记 visited），然后挨个把未访问的邻居递归下去；所有邻居都处理完，函数结束，控制权自然交还给上一层。这个”自然交还”就是回退。

代码里我故意写了两个”输出 u”：一个在进入时，一个在离开时。前者发生在前序位置，后者发生在后序位置。这个区分极其重要：前序是”刚到访”，后序是”要走了”，同一段代码放在不同位置，效果天差地别。比如求连通分量大小，在前序位置计数即可；做拓扑排序，往往要在后序位置收答案。第 5 节讲时间戳时，这两个位置会升级成”发现时间”和”完成时间”。

2.2 TypeScript / JavaScript 实现

假设图用邻接表存储：graph 是一个数组，graph[u] 存放顶点 u 的所有邻居。下面是完整的实现：

function dfs(graph: number[][], start: number): number[] {
  const visited: boolean[] = new Array(graph.length).fill(false);
  const order: number[] = [];

  function visit(u: number): void {
    visited[u] = true;        // 进入时立即标记
    order.push(u);            // 前序位置：记录访问顺序
    for (const v of graph[u]) {
      if (!visited[v]) {
        visit(v);             // 钻进未访问的邻居
      }
    }
    // 后序位置：这里什么也不做，函数返回即回溯
  }

  visit(start);
  return order;
}

如果图可能不连通，我们通常在外面套一层循环，确保每个顶点都被访问到：

function dfsAll(graph: number[][]): number[] {
  const visited: boolean[] = new Array(graph.length).fill(false);
  const order: number[] = [];

  function visit(u: number): void {
    visited[u] = true;
    order.push(u);
    for (const v of graph[u]) {
      if (!visited[v]) visit(v);
    }
  }

  for (let u = 0; u < graph.length; u++) {
    if (!visited[u]) visit(u);  // 每个未访问顶点都发起一次 DFS
  }
  return order;
}

外层循环的意义是：图不一定连通，从一个起点出发可能只覆盖一个连通分量。想遍历整张图，就必须对每个”还没被访问过”的顶点再发起一次 DFS。这也顺便解释了 DFS 为什么能数连通分量——第 6 节会细说。

2.3 visited 的标记时机：进入时标记，为什么？

这是 DFS 初学者最容易踩的坑。对比两种写法：

写法一（推荐）：

function visit(u: number): void {
  visited[u] = true;   // 一进门就标记
  for (const v of graph[u]) {
    if (!visited[v]) visit(v);
  }
}

写法二（有坑）：

function visit(u: number): void {
  for (const v of graph[u]) {
    if (!visited[v]) {
      visit(v);
      visited[v] = true;  // 从子调用返回后才标记？
    }
  }
}

写法二的问题非常隐蔽。设想无向图 A — B — C，从 A 开始。A 先访问 B，递归进入 B；B 检查邻居 A（已访问？还没！因为 A 的标记放在子调用返回之后）、C（未访问），于是 B 又递归进入 A；A 再进入 B……两个函数互相调用，永远没有终止。这正是”访问后标记”的致命伤：标记太晚，等于没标记。

再换一种写法二的具体形态：

function visit(u: number): void {
  if (visited[u]) return;
  for (const v of graph[u]) {
    visit(v);
    visited[u] = true;
  }
}

这个版本同样不对：进入 u 时没有立刻标记，u 的多个邻居可能在 u 标记完成之前重复递归 u。更糟的是，如果 u 是叶子（没有邻居），visited[u] 永远不会被置真。

那为什么标准写法要求”一进门就标记”？原因有三：

第一，防止同一条边被双向反复触发。无向图中 u 和 v 互为邻居，u 调 visit(v) 时，v 的第一件事就是检查自己的邻居列表，如果 u 没被标记，v 会立刻调 visit(u)，形成 A → B → A → B 的无限循环。只有进入 u 的瞬间就把 u 写进名单，v 在检查邻居时才能看到”u 已访问”。

第二，保证每个顶点只被递归一次。标记放在循环外面，意味着无论 u 有几个邻居路径通向它，它都只会在第一次被发现时被处理。DFS 的 O(V + E) 复杂度正是建立在这条保证上。

第三，语义上更准确。visited 的含义是”我已经来过这里”，而不是”我走完了这里”。当你还在 u 内部递归时，u 就已经处于”访问中”状态，所以从进入那一刻起就应该生效。这个概念到第 5 节会升级为”灰色”与”黑色”两种状态：灰色表示正在访问中，黑色表示访问完成。

还有一个小问题值得顺便澄清：既然函数开头可以检查 if (visited[u]) return;，为什么实现里没写？因为调用方已经用 if (!visited[v]) 过滤过了，正常流程不会重复进入。不过加上开头检查也不会错，反而让函数更健壮——比如外层循环和递归调用同时存在时，防御性检查能避免边界情况。两种风格各有拥趸，核心原则不变：标记必须发生在进入函数后、遍历邻居前。

2.4 递归的代价与风险

递归版代码最美，但有两个现实问题。第一，函数调用栈有深度限制。JavaScript 引擎通常允许几万层到十几万层递归（不同环境差异很大），一旦图的路径很长——比如一条链 10 万个顶点——递归就会栈溢出。第二，每次递归调用都有开销：参数压栈、返回地址、局部变量，都会占用内存和时间。比赛和工程里，当图规模很大或路径可能很深时，往往会改用迭代版（第 4 节）。但作为理解工具，递归版无可替代：它把”回溯”直接映射为函数返回，概念上零损耗。

2.5 visited 的三种颜色：白、灰、黑

前面只用了两种状态：未访问 / 已访问。但某些算法需要知道”这个顶点是不是还在递归栈里”，于是把已访问拆成两半：灰色（访问中，还没返回）和黑色（访问完成）。三态标记在有向图的环检测、强连通分量算法里是标配：

白色：还没被 DFS 碰到过
灰色：正在 DFS 的递归栈中（进入了，但还没返回）
黑色：DFS 已经彻底处理完（所有邻居都探索过了）

递归代码里，置灰发生在进入函数时，置黑发生在函数返回前：

function dfsWithColor(graph: number[][], start: number): void {
  const color: number[] = new Array(graph.length).fill(0); // 0 白，1 灰，2 黑

  function visit(u: number): void {
    color[u] = 1;                       // 进入：置灰
    for (const v of graph[u]) {
      if (color[v] === 0) {
        visit(v);                       // 白色：还没去过，递归
      } else if (color[v] === 1) {
        // 灰色：v 还在栈中，是 u 的祖先 → 有向回边 → 有环
      }
    }
    color[u] = 2;                       // 离开：置黑
  }

  visit(start);
}

颜色不是花架子，它给 DFS 增加了一个非常重要的信息维度：“现在栈里还有谁”。两个顶点如果同为灰色，就意味着它们在当前递归路径上是祖先-后代关系。这个”在栈中”的判定，是无向图与有向图环检测差异的根源（第 6 节会细讲），也是括号性质（第 5 节）能够成立的直观原因。

2.6 一个常见误解：visited 能不能省掉？

初学者常问：“如果图本身没有环，visited 是不是就可以不要了？“答案分情况：

如果图是树（无环且连通），确实可以不要 visited——树系列第 5 篇就是这么干的。但哪怕是无环的有向无环图，visited 依然必要！因为两个不同的祖先可能共享同一个后代。比如 A → C 和 B → C，从 A 出发 DFS 会访问 C，从 B 出发又会访问 C 一次。虽然不会死循环，但同一个顶点被重复进入，复杂度从 O(V + E) 退化成指数级，很多问题的答案也会被算重。

所以更准确的说法是：visited 的第一作用是防环，第二作用是防重复。在一般图上，两个作用缺一不可。只有当你明确知道每个顶点只会被一条路径到达（树、DAG 的特殊子类），才谈得上省略。

2.7 递归调用的内存里到底发生了什么？

理解递归版 DFS 的调用栈，对后面手算走查非常重要，这里提前把底牌揭开。每次调用 visit(u)，JavaScript 引擎会创建一块栈帧，里面存放：函数的局部变量（visited 引用、graph 引用、循环变量等）、参数 u、返回地址（调用结束后跳回哪里）。visit(0) 调用 visit(1) 时，visit(0) 的栈帧不会被销毁，而是完整保存在栈里，等着 visit(1) 返回后继续执行。

这就是”回溯”的物理本质：递归返回不是重新计算，而是把保存好的旧状态重新激活。visit(1) 返回后，visit(0) 的循环变量还停在”刚处理完邻居 1”的位置，所以它接着处理邻居 2——不需要任何额外代码，系统帮你记住了走到哪一步。

把栈帧画出来：

flowchart TD
    F0["visit(0)：循环到邻居 1，暂停"]
    F1["visit(1)：循环到邻居 3，暂停"]
    F2["visit(3)：循环到邻居 2，暂停"]
    F3["visit(2)：循环到邻居 4，暂停"]
    F0 --> F1 --> F2 --> F3

每一层栈帧都保存着”自己的进度”，最深的栈帧最先恢复执行，执行完销毁，上一帧接着跑。这也解释了为什么递归版 DFS 和”迭代器栈”版在行为上完全等价——迭代器栈里的 [顶点, 下一个邻居下标] 就是栈帧的简化版。

2.8 从一次 DFS 到遍历全图

前面实现里，外层 for 循环让 DFS 覆盖所有顶点。这引出一个重要的视角转变：单次 DFS 只能探索”从起点可达的世界”。在有向图里，“可达”还是单向的——从 0 出发能到 1，不代表从 1 出发能到 0。所以：

• 无向图：一次 DFS 覆盖一个连通分量；
• 有向图：一次 DFS 覆盖一个”从起点可达的顶点集合”，它可能比强连通分量大，也可能比强连通分量小；
• 想探索完整张有向图，必须从每个未访问顶点再发起 DFS。

下面这张有向图，从 0 出发只能到达 0、1、2；顶点 3 只能从 3 自己到达，需要第二次 DFS：

graph LR
    0["0"] --> 1["1"] --> 2["2"]
    2 --> 1
    3["3"]

所以 dfsAll 的循环不是”锦上添花”，而是”图可能不连通”这个事实的必然要求。后面数连通分量、做拓扑排序、求强连通分量，全都建立在这个全图循环之上。

2.9 最小例子：三顶点图上的代码走查

光看代码不如亲手走一遍。拿最简单的三角形 A — B — C — A（顶点编号 0、1、2，0 连 1 和 2，1 连 2）来跑递归版：

graph LR
    0["0"] --- 1["1"]
    1 --- 2["2"]
    2 --- 0["0"]

调用 visit(0)：标记 0，输出 0；邻居 1 未访问，调用 visit(1)。visit(1)：标记 1，输出 1；邻居 0 已访问跳过，邻居 2 未访问，调用 visit(2)。visit(2)：标记 2，输出 2；邻居 1、0 都已访问，跳过；函数返回。回到 visit(1)：没有更多邻居，返回。回到 visit(0)：邻居 2 已访问，跳过；返回。输出 0 → 1 → 2。

现在关键问题来了：如果 visited 是”访问后标记”会怎样？ 调用 visit(0) 不标记，直接遍历邻居：邻居 1 未访问，调用 visit(1)；visit(1) 遍历邻居：邻居 0 未访问！调用 visit(0)；visit(0) 又遍历邻居：邻居 1 未访问……两个函数互相咬住，永不终止。即使你足够幸运没有死循环，重复访问也会让输出出现大量重复顶点。这个最小例子把第 2.3 节的所有道理浓缩成了三行代码——建议你自己在纸上把两种版本各走一遍，感受会完全不同。

再补一个观察：三角形里三条边，DFS 只走了两条（0-1 和 1-2），第三条 2-0 在访问 2 时被发现”0 已访问”而跳过。这就是第 5 节说的回边：它和树边一起构成一个环。一个 3 顶点的三角形，DFS 树恰好只有 2 条边——验证了”连通图的 DFS 树边数 = 顶点数减一”这个规律。

现在我们已经有了代码，但代码是一回事，理解是另一回事。下一节我们拿一张真实的图，把每一步递归调用栈的变化画出来。

3 手算走查：一张具体的图，完整走一遍

3.1 主角登场：六顶点无向图

为了让走查既能看到”钻深”又能看到”回头”，我们选一张有环、有分支的无向图。顶点是 0 到 5，邻接表如下：

0: 1, 2
1: 0, 3
2: 0, 3, 4
3: 1, 2, 5
4: 2, 5
5: 3, 4

画出来是这样：

graph LR
    0["0"] --- 1["1"]
    0 --- 2["2"]
    1 --- 3["3"]
    2 --- 3["3"]
    2 --- 4["4"]
    3 --- 5["5"]
    4 --- 5["5"]

这图里有三个环：0-1-3-2-0、2-3-5-4-2、0-2-4-5-3-1-0（外面的大环），还有几条共享的边。用它来走查，回边、分支、回溯一次全齐了。

约定：从顶点 0 出发，邻居按编号从小到大检查。也就是说，在顶点 2 时先看 0、再看 3、再看 4。

3.2 完整走查：十六个关键瞬间

第 1 步：调用 dfs(0)。0 未访问，标记 0，输出 0。0 的第一个邻居是 1，未访问，于是递归 dfs(1)。此时调用栈是 [0, 1]（栈底在左，栈顶在右）。

第 2 步：dfs(1) 标记 1，输出 1。1 的邻居是 0 和 3。0 已访问，跳过；3 未访问，递归 dfs(3)。调用栈变成 [0, 1, 3]。

第 3 步：dfs(3) 标记 3，输出 3。3 的邻居是 1、2、5。1 已访问，跳过；2 未访问，递归 dfs(2)。调用栈变成 [0, 1, 3, 2]。

第 4 步：dfs(2) 标记 2，输出 2。2 的邻居是 0、3、4。0 已访问，跳过；3 已访问，跳过；4 未访问，递归 dfs(4)。调用栈变成 [0, 1, 3, 2, 4]。

第 5 步：dfs(4) 标记 4，输出 4。4 的邻居是 2、5。2 已访问，跳过；5 未访问，递归 dfs(5)。调用栈变成 [0, 1, 3, 2, 4, 5]，深度达到 6，全部顶点都进去了。

第 6 步：dfs(5) 标记 5，输出 5。5 的邻居是 3、4，全都已访问，没有可递归的邻居。函数结束，返回。调用栈退回 [0, 1, 3, 2, 4]。

第 7 步：回到 dfs(4)。4 的邻居列表检查完了，函数结束，返回。调用栈退回 [0, 1, 3, 2]。

第 8 步：回到 dfs(2)。2 的邻居也全检查完了，返回。调用栈退回 [0, 1, 3]。

第 9 步：回到 dfs(3)。继续检查 3 的邻居列表——刚才在 5 没被访问时我们还没有轮到它，现在轮到 5 了：5 已访问，跳过。邻居列表结束，dfs(3) 返回。调用栈退回 [0, 1]。

第 10 步：回到 dfs(1)。1 的邻居检查完毕，返回。调用栈退回 [0]。

第 11 步：回到 dfs(0)。0 的邻居列表中 1 已经处理完，接下来是 2：2 已访问，跳过。邻居列表结束，dfs(0) 返回。调用栈为空，整个 DFS 结束。

最终访问顺序是：0 → 1 → 3 → 2 → 4 → 5。

值得注意：虽然图有 6 个顶点、7 条边，但整个过程中 dfs 函数只被调用了 6 次——恰好每个顶点一次。剩下没有被递归走到的边（0-2、1-3、3-5、4-5 这四条）都只是被”看了一眼”，发现对方已访问就跳过了。被递归走到的边是 0-1、1-3、3-2、2-4、4-5，一共 5 条，恰好构成一棵连接全部 6 个顶点的树——DFS 树！我们到第 5 节再细看它。

3.3 递归调用栈变化图

把上面十六步浓缩成调用栈的六帧关键状态：

flowchart LR
    subgraph S1["第 1 步"]
        A1["栈底 0"]
    end
    subgraph S2["第 2 步"]
        A2["0 → 1"]
    end
    subgraph S3["第 3 步"]
        A3["0 → 1 → 3"]
    end
    subgraph S4["第 4 步"]
        A4["0 → 1 → 3 → 2"]
    end
    subgraph S5["第 5 步"]
        A5["0 → 1 → 3 → 2 → 4"]
    end
    subgraph S6["第 6 步"]
        A6["0 → 1 → 3 → 2 → 4 → 5"]
    end
    S1 --> S2 --> S3 --> S4 --> S5 --> S6

这是”钻深”方向：栈一层层长高，每入栈一个顶点，就代表深入了一层。接下来是”回头”方向：

flowchart LR
    subgraph R1["第 6 步后"]
        B1["0 → 1 → 3 → 2 → 4 → 5"]
    end
    subgraph R2["第 7 步"]
        B2["0 → 1 → 3 → 2 → 4"]
    end
    subgraph R3["第 8 步"]
        B3["0 → 1 → 3 → 2"]
    end
    subgraph R4["第 9 步"]
        B4["0 → 1 → 3"]
    end
    subgraph R5["第 10 步"]
        B5["0 → 1"]
    end
    subgraph R6["第 11 步"]
        B6["0"]
    end
    R1 --> R2 --> R3 --> R4 --> R5 --> R6

把两张图连起来看，就是完整的故事：先一路入栈到最深，再一路出栈回到底。每个顶点的”生命周期”像括号一样嵌套：dfs(0) 包含 dfs(1)，dfs(1) 包含 dfs(3)，dfs(3) 包含 dfs(2)，dfs(2) 包含 dfs(4)，dfs(4) 包含 dfs(5)。这种嵌套关系不是巧合，它正是 DFS 树的结构，也是后序位置”先深后浅”的原因。

请特别注意第 6 帧和第 7 帧之间的转变：栈从最深（6 层）开始收缩时，最先离开的是最后进入的顶点 5。这就像一个叠罗汉的队伍，最后站上来的人最先离场——后进先出，栈的铁律。整个 DFS 的”深度”是多少，看的就是这个栈在任何时刻的高度；本例最高 6 层，恰好等于顶点总数，说明图被走成了一条贯穿全部的路径。

3.4 一张步骤总表

把关键步骤整理成表，方便对照：

步骤	动作	当前顶点	输出	递归调用栈（栈底→栈顶）
1	进入 0	0	0	[0]
2	0 发现 1 未访问，递归	1	1	[0, 1]
3	1 发现 3 未访问，递归	3	3	[0, 1, 3]
4	3 发现 2 未访问，递归	2	2	[0, 1, 3, 2]
5	2 发现 4 未访问，递归	4	4	[0, 1, 3, 2, 4]
6	4 发现 5 未访问，递归	5	5	[0, 1, 3, 2, 4, 5]
7	5 无未访问邻居，返回	4	—	[0, 1, 3, 2, 4]
8	4 无未访问邻居，返回	2	—	[0, 1, 3, 2]
9	2 无未访问邻居，返回	3	—	[0, 1, 3]
10	3 的邻居 5 已访问，返回	1	—	[0, 1]
11	1 无未访问邻居，返回	0	—	[0]
12	0 的邻居 2 已访问，返回	—	—	[]

看到表里”输出”列的变化了吗？前 6 步都在输出，后 6 步一个输出都没有。这是纯前序版 DFS 的特点：所有顶点在”进入”时就被记录，回溯阶段只是收尾。如果我们把输出放到后序位置，得到的就是完全相反的节奏——先一路钻到底，然后从最深处开始逐层”报告完成”。这个差异第 5 节讲时间戳时会再次出现。

3.5 换个邻居顺序会怎样？

邻接表里邻居的顺序会影响访问顺序。如果第 3 步在顶点 3 先看到 5，那么 DFS 会先走 0 → 1 → 3 → 5 → 4 → 2，得到另一棵 DFS 树。这说明一个很重要的点：DFS 树依赖图的表示方式和遍历顺序，同一张图可以有多个合法的 DFS 树。所以讨论”DFS 会输出什么顺序”时，一定要先说明邻接表长什么样。这个”顺序依赖”不是缺陷，而是特性——很多算法（比如拓扑排序、强连通分量）正是利用 DFS 的某种特定顺序来提取信息。

3.6 前序顺序和后序顺序，各是什么模样？

第 3.4 节我们只输出了前序顺序。现在把同一张图分别按前序和后序输出，对比一下：

前序（发现顺序）：0 → 1 → 3 → 2 → 4 → 5

后序（完成顺序）：5 → 4 → 2 → 3 → 1 → 0

注意观察两个规律。第一，后序顺序恰好是前序的”压缩镜像”：先完成的是最深的顶点 5，最后完成的是最浅的根 0。第二，后序顺序里，任何祖先都排在所有后代之后——0 在最后，1 在倒数第二，3 在倒数第三。这个”子先父后”的次序正是拓扑排序和强连通分量算法的核心原料。

用一棵”完成顺序树”来表示后序：

graph BT
    5["5（第 1 个完成）"] --> 4["4（第 2 个完成）"]
    4 --> 2["2（第 3 个完成）"]
    2 --> 3["3（第 4 个完成）"]
    3 --> 1["1（第 5 个完成）"]
    1 --> 0["0（第 6 个完成）"]

如果把”完成”理解成”交卷”，后序位置就是”所有作业都做完后签字离场”。DFS 进入时不知道子树里有什么，只有等子树全部返回，才拥有完整信息——这就是为什么”汇总类”操作必须放在后序位置。

3.7 有向图的手算：方向改变了什么？

第 3 节的走查用的是无向图。有向图的手算原则上完全一样，只是邻居列表变成”出边指向的顶点”。但有一个新现象值得注意：有向图里，从起点出发可能根本到不了某些顶点。我们改一版例子，把边改成单向的：

0 → 1, 0 → 2
1 → 3
2 → 3
3 → 4
5 → 3（指向 3，但 5 不能被 3 到达）

从 0 出发，DFS 依次走 0 → 1 → 3 → 4，然后回到 0 再走 2（2 的邻居 3 已访问）。最终 0、1、2、3、4 都被访问，但顶点 5 完全没被碰到——因为没有任何一条从 0 出发的路径能到达 5。要访问 5，必须依赖外层循环：

graph LR
    0["0"] --> 1["1"] --> 3["3"] --> 4["4"]
    0 --> 2["2"]
    2 --> 3
    5["5"] --> 3

这个例子再次提醒我们：在有向图上，DFS 的”势力范围”是可达集，不是全图。判断”从 u 能否到达 v”正是利用这个性质：从 u 发起 DFS，看 v 是否被标记。这也是可达性问题最简单的解法。

3.8 走查的”时间线”视角

第 3.4 节的表格是按步骤看的，现在我们换成”时间线”视角：把时间分成一格一格，每格标注”发生了什么”。这样能更直观地看到发现和完成如何交错：

flowchart LR
    T1["t1 发现0"] --> T2["t2 发现1"] --> T3["t3 发现3"] --> T4["t4 发现2"]
    T4 --> T5["t5 发现4"] --> T6["t6 发现5"] --> T7["t7 完成5"]
    T7 --> T8["t8 完成4"] --> T9["t9 完成2"] --> T10["t10 完成3"]
    T10 --> T11["t11 完成1"] --> T12["t12 完成0"]

注意时间线上两个有趣的现象。第一，前六格全是”发现”，后六格全是”完成”——因为图连通且 DFS 从 0 出发一次就覆盖了全部顶点，发现阶段一口气完成，完成阶段一口气回溯。第二，发现顺序和完成顺序正好相反：先发现的 0 最后完成，最后发现的 5 最先完成。这就是栈的 LIFO 特性在时间轴上的投影：越晚入栈的越早出栈。

如果图里还有分支，时间线会呈现”发现-完成-发现-完成”交错的样子。比如在顶点 3 有另一棵子树 6、7，那么 3 发现后会先完成 6、7，再继续完成 3。这种交错正是第 5 节”区间嵌套”的来源，也是理解时间戳最好的训练素材。

现在递归版已经彻底吃透了。下一节我们把它翻译成迭代版。

4 迭代实现：用显式栈模拟递归

4.1 栈：为什么是栈？

递归版里，系统帮你维护了一个调用栈：每次递归，当前函数的局部状态（走到哪个邻居了）被压进栈；函数返回，状态被弹出。迭代版要做的，就是自己准备一个栈，把这个过程显式地做出来。

回忆 BFS 用队列的原因：FIFO 让”先发现的人先被处理”，于是访问按层扩散。DFS 要的是”后进来的先处理”——刚发现的邻居必须优先于更早入栈的顶点被深入。这正是栈（Stack）的语义：LIFO，后进先出。队列管广度，栈管深度，这是两个算法最核心的结构差异。

举个生活例子：你有一摞盘子，洗完一个放一个，用时永远先拿最上面的——后放的先拿。DFS 的显式栈就是这样一摞”待探索任务”。

4.2 朴素迭代版及其与递归版的顺序差异

最直观的迭代写法：

function dfsIterative(graph: number[][], start: number): number[] {
  const visited: boolean[] = new Array(graph.length).fill(false);
  const order: number[] = [];
  const stack: number[] = [start];

  while (stack.length > 0) {
    const u = stack.pop()!;        // 栈顶出栈
    if (visited[u]) continue;      // 出栈时再查一次
    visited[u] = true;
    order.push(u);
    for (const v of graph[u]) {
      if (!visited[v]) {
        stack.push(v);             // 未访问邻居全部入栈
      }
    }
  }
  return order;
}

这段代码能跑，访问顺序也合法，但仔细对照递归版会发现一个微妙差异。递归版在顶点 0 时，先递归 1，把 1 整棵子树走完，才轮到 2；而上面的迭代版把 0 的所有邻居（1、2）都压进栈，出栈顺序是反的——先出 2，再出 1。也就是说，如果递归版按邻居顺序 1、2 深入，朴素迭代版会先处理 2。

为什么会这样？因为递归是”遇到一个未访问邻居，立刻丢下当前顶点的剩余邻居，钻进那个邻居”；而朴素迭代是”先把当前顶点的所有邻居登记到任务栈，再逐个执行”。一个边发现边钻，一个批量入栈。两者都满足”深度优先”的大原则，但微小的顺序不同。

用一张图直观展示差异。假设起点 0 的邻居是 1 和 2，1 的邻居是 3：

flowchart TD
    subgraph Rec["递归版：遇到就钻"]
        R1["0 → 1 → 3 走完，回头 → 2"]
    end
    subgraph Iter["朴素迭代版：批量入栈，反序出栈"]
        I1["栈 [1, 2]，先弹 2"]
        I2["再弹 1 → 3"]
    end

4.3 如何让迭代版和递归版顺序完全一致

想让迭代版和递归版输出一模一样，有两个办法。

办法一：反向压栈。递归版按邻居正序 1、2 依次递归，等价于先处理 1。栈是 LIFO，所以只要把邻居反着压入（先压 2、后压 1），出栈就是 1 先出：

function dfsIterativeSameOrder(graph: number[][], start: number): number[] {
  const visited: boolean[] = new Array(graph.length).fill(false);
  const order: number[] = [];
  const stack: number[] = [start];

  while (stack.length > 0) {
    const u = stack.pop()!;
    if (visited[u]) continue;
    visited[u] = true;
    order.push(u);
    for (let i = graph[u].length - 1; i >= 0; i--) {
      const v = graph[u][i];
      if (!visited[v]) stack.push(v);
    }
  }
  return order;
}

这个技巧在竞赛代码里很常见：想复制递归版的顺序，就把邻居倒着入栈。

办法二：栈里存”迭代器”。栈元素不只是顶点，而是”顶点 + 下一个要处理的邻居下标”。出栈后不是立刻访问新顶点，而是继续当前顶点的邻居循环——这才真正模拟了递归的”局部变量”。实现如下：

function dfsIterativeWithIterator(graph: number[][], start: number): number[] {
  const visited: boolean[] = new Array(graph.length).fill(false);
  const order: number[] = [];
  const stack: Array<[number, number]> = [[start, 0]];
  visited[start] = true;

  while (stack.length > 0) {
    const [u, i] = stack[stack.length - 1];
    if (i < graph[u].length) {
      const v = graph[u][i];
      stack[stack.length - 1][1] = i + 1;   // 记录进度
      if (!visited[v]) {
        visited[v] = true;
        order.push(v);
        stack.push([v, 0]);                  // 进入 v
      }
    } else {
      stack.pop();                           // u 的所有邻居处理完，回溯
    }
  }
  return order;
}

注意这个版本的顺序和递归版严格一致：当栈顶是 [0, 0] 时，先看邻居 1，把 [1, 0] 压栈；等 1 的子树全部完成、[1, 0] 弹出后，栈顶变回 [0, 1]，继续处理邻居 2。后序位置也天然存在——stack.pop() 那一行就是”u 即将离开”的时刻，和第 5 节的时间戳完美对应。

三种写法的取舍：

版本	顺序与递归版一致	代码复杂度	后序位置	适用场景
递归	—	最低	天然存在	理解、深度可控
朴素迭代	不一致	低	无	只求遍历顺序
反向压栈	一致（前序）	低	无	要前序顺序、怕栈溢出
迭代器栈	完全一致	中	有	要后序、深度不可控

4.4 迭代版的栈状态走查

还用第 3 节那张图，用朴素迭代版从 0 出发走一遍。初始栈 [0]。出栈 0，标记，把 0 的邻居 1、2 压入，栈变为 [1, 2]（栈顶在右）。出栈 2，标记，把 2 的邻居 0、3、4 中未访问的压入，栈变为 [1, 4, 3]（0 已访问不入栈）。出栈 3，标记，把 3 的邻居 1、2、5 中未访问的 5 压入，栈变为 [1, 4, 5]。出栈 5，标记，5 的邻居 3、4 都已访问，不入栈，栈变为 [1, 4]。出栈 4，标记，4 的邻居 2、5 都已访问，栈变为 [1]。出栈 1，标记，1 的邻居 0、3 都已访问，栈为空。访问顺序：0 → 2 → 3 → 5 → 4 → 1。

把栈状态画成序列：

flowchart LR
    C1["栈 [0]"]
    C2["栈 [1,2]"]
    C3["栈 [1,4,3]"]
    C4["栈 [1,4,5]"]
    C5["栈 [1,4]"]
    C6["栈 [1]"]
    C7["栈 []"]
    C1 --> C2 --> C3 --> C4 --> C5 --> C6 --> C7

对比第 3 节递归版的调用栈：[0] → [0,1] → [0,1,3] → [0,1,3,2] → [0,1,3,2,4] → [0,1,3,2,4,5]。递归版总是”一条线”越走越深，迭代版却经常同时存在多个等待中的顶点——这就是”批量入栈”和”边发现边钻”的区别。

4.5 什么时候选迭代版？

三个信号：一是图的深度可能超过递归上限（超长链、超大树、某些状态空间搜索）；二是环境对递归不友好（有些嵌入式环境栈极小）；三是你需要完全掌控”后序位置”的行为（迭代器栈版）。如果只是写算法题，递归版通常够用，而且可读性最好。记住：先用递归想清楚，再用迭代优化。

4.6 迭代版的空间与性能

迭代版和递归版的时间复杂度都是 O(V + E)，空间上略有差别：递归版的空间是”调用栈 + visited 数组”，迭代版是”显式栈 + visited 数组”。数量级相同，但显式栈有两个实际好处。

第一，可控。递归栈的深度由引擎决定，溢出前你没有任何提示；显式栈的深度自己心里有数，甚至可以在压栈前检查栈大小，超过阈值就切换策略（比如改用 BFS 或分块处理）。第二，可复用。同一个栈对象可以反复使用，避免频繁创建调用帧带来的开销，在性能敏感的循环里更友好。

不过，迭代版也有一处容易踩的坑：朴素迭代版把”已访问”检查放在出栈时，这意味着同一个顶点可能被压入多次。极端情况下，一个高扇出的顶点被 N 个邻居各自发现一次，栈里会同时存在 N 份相同顶点，空间在最坏情况下变成 O(E) 而不是 O(V)。解决办法是”入栈时检查 + 标记”，即压栈前确认未访问并立即标记：

function dfsIterativeMarkOnPush(graph: number[][], start: number): number[] {
  const visited: boolean[] = new Array(graph.length).fill(false);
  const order: number[] = [];
  const stack: number[] = [start];
  visited[start] = true;

  while (stack.length > 0) {
    const u = stack.pop()!;
    order.push(u);
    for (const v of graph[u]) {
      if (!visited[v]) {
        visited[v] = true;   // 入栈即标记
        stack.push(v);
      }
    }
  }
  return order;
}

这个版本栈里不会出现重复顶点，空间保证 O(V)。代价是它和递归版的顺序差异更大（每个顶点在其父顶点出栈时就被”预订”了，而不是等到真正弹出时才标记），但对大多数只关心”遍历结果”的场景完全够用。三种标记策略——出栈标记、入栈标记、迭代器栈——没有绝对的对错，选哪种取决于你要的是”防重复”还是”严格复刻递归顺序”。

好，实现层面讲完了。但 DFS 真正的威力，要等我们给它配上”时间戳”和”DFS 树”这两个分析工具才能完全释放。

4.7 递归版与迭代版：同一枚硬币的两面

很多初学者纠结”到底该记递归版还是迭代版”，其实两者是同一枚硬币的两面。递归版用系统调用栈，迭代版用手写栈；递归版的”函数返回”就是迭代版的”出栈”，递归版的”递归调用”就是迭代版的”入栈”。任何递归 DFS 都可以机械地翻译成迭代 DFS，反之亦然。

翻译的通用步骤：

1. 递归函数的参数列表 → 栈元素的字段
2. 递归调用处 → 入栈（携带新参数）
3. 函数返回处 → 出栈
4. 局部变量（比如"循环到第几个邻居"）→ 栈元素里的附加字段

以 visit(u) 为例，参数是 u，局部变量是邻居下标 i，所以栈元素是 [u, i]——这正是第 4.3 节迭代器栈的由来。掌握了这四步，你就能在任何语言里自如地互相转换，而不是死记两套代码。

还有一个值得记住的对称性：BFS 的迭代版天生就是循环 + 队列，DFS 的迭代版需要手动管理栈。为什么 BFS 很少提递归版？因为 BFS 的”按层处理”和递归的”深入优先”气质不合，硬写递归 BFS 需要额外传层号，别扭且容易错。这也从侧面说明：DFS 天然亲近递归，BFS 天然亲近循环。

最后提醒一句：考试和面试中，递归版 DFS 通常是默认答案，因为它最短、最不容易写错；只有在题目明确说明图很深（比如 10 万级链）或要求后序位置时，才主动切换到迭代版。两种都要会写，但”默认递归、按需迭代”是最稳的策略。

5 DFS 树与时间戳：把探索过程变成可分析的结构

5.1 什么是 DFS 树

回顾第 3 节的走查：6 个顶点、7 条边，DFS 实际”走”的边只有 5 条，其余 2 条只是被检查了一下。被真正走到的边，恰好把全部顶点连成一棵树——这就是DFS 树。如果图不连通，每次从外层循环发起的 DFS 各生成一棵树，合起来叫 DFS 森林。

我们的例子里，DFS 树长这样（实线是树边，虚线是没被走到的边）：

graph TD
    0["0"] --> 1["1"]
    1 --> 3["3"]
    3 --> 2["2"]
    2 --> 4["4"]
    4 --> 5["5"]
    0 -. "非树边 0-2" .-> 2
    1 -. "非树边 1-3" .-> 3
    3 -. "非树边 3-5" .-> 5
    4 -. "非树边 4-5" .-> 5

DFS 树不是随便挑的生成树，它忠实记录了遍历的”家族关系”：dfs(0) 调用了 dfs(1)，所以 1 是 0 的孩子；dfs(1) 调用了 dfs(3)，所以 3 是 1 的孩子。栈的嵌套关系，就是树的父子关系。这就是为什么第 3 节说”括号嵌套不是巧合”。

5.2 发现时间与完成时间

现在给 DFS 装上计时器。用一个全局计数器，在每次进入一个顶点时记一个”发现时间”（discovery time，简称 d），在每次离开（所有邻居处理完，函数返回）时记一个”完成时间”（finish time，简称 f）。修改后的递归版：

function dfsWithTime(graph: number[][]): void {
  const n = graph.length;
  const visited: boolean[] = new Array(n).fill(false);
  const discovery: number[] = new Array(n).fill(-1);
  const finish: number[] = new Array(n).fill(-1);
  let timer = 0;

  function visit(u: number): void {
    visited[u] = true;
    discovery[u] = ++timer;      // 发现时间：进入 u 时
    for (const v of graph[u]) {
      if (!visited[v]) visit(v);
    }
    finish[u] = ++timer;         // 完成时间：离开 u 时
  }

  for (let u = 0; u < n; u++) {
    if (!visited[u]) visit(u);
  }
}

对我们的例图跑一遍，得到：

顶点	发现时间 d	完成时间 f	时间区间
0	1	12	[1, 12]
1	2	11	[2, 11]
3	3	10	[3, 10]
2	4	9	[4, 9]
4	5	8	[5, 8]
5	6	7	[6, 7]

把每个顶点画成一条时间线，起始点是发现时间，终点是完成时间：

timeline
    title DFS 时间戳：每条线段 = 一个顶点的"在栈期间"
    0 : d=1 : f=12
    1 : d=2 : f=11
    3 : d=3 : f=10
    2 : d=4 : f=9
    4 : d=5 : f=8
    5 : d=6 : f=7

看这个时间线，会发现一个绝妙的规律：任何两个顶点的时间区间要么互不重叠，要么完全嵌套——绝不可能交叉。比如 [1,12] 完全包含 [2,11]，[2,11] 完全包含 [3,10]，而 [6,7] 完全包含在 [5,8] 里。为什么？因为 DFS 是深度优先的：一个顶点一旦被进入，它的整个子树会被一口气探索完，之后才轮到其他顶点。这种”要么包含、要么不相交”的性质，叫作括号性质（parenthesis property），因为时间区间就像括号一样嵌套：0 ( 1 ( 3 ( 2 ( 4 ( 5 ) ) ) ) )。

括号性质有什么用？它给了我们一个判断祖先关系的利器：如果 u 是 v 的祖先，当且仅当 d[u] < d[v] < f[v] < f[u]。换句话说，区间包含 = 祖先后代，区间分离 = 各自独立。这个性质后面推导强连通分量时会被反复使用。

为什么时间区间只能嵌套、不能交叉？

用反证法想清楚这个问题，比背结论有用得多。假设两个顶点 u 和 v 的区间交叉，即 d[u] < d[v] < f[u] < f[v]。v 是在 u 的递归过程中被发现的（因为 d[v] 落在 u 的区间里）。DFS 的原则是深度优先：一旦进入 v，就必须把 v 的整个子树探索完，v 才会返回。u 的调用还压在栈底等着 v 返回，所以 f[u] 不可能发生在 v 返回之前——f[v] < f[u] 才是必然。这就和假设矛盾。

所以”要么嵌套、要么分离”不是 DFS 的巧合，而是”深度优先”四个字的结构性后果。任何具备”先深入后返回”性质的遍历，都会有类似的括号结构。这个性质在算法分析里被反复使用：判断祖先、划分子树、识别回边，全都建立在时间区间之上。

时间戳的另一个视角：括号序列

把发现时间记成左括号”(“、完成时间记成右括号”)“，DFS 的过程就变成一个合法的括号序列：

0( 1( 3( 2( 4( 5( 5) 4) 2) 3) 1) 0)

读一下这个序列：每个顶点出现两次，第一次是进入，第二次是离开；左括号和右括号的配对方式严格嵌套，和递归调用一一对应。这个视角有两个直接推论。

推论一：子树的顶点在序列里是连续的一段。顶点 3 的子树（3、2、4、5）从 3( 开始，到 3) 结束，中间不会有任何”外来”顶点。这是因为 DFS 进入 3 后，会一口气处理完整个子树才返回。

推论二：回边判断可以翻译成区间关系。u → v 是回边，等价于 v 的区间包含 u 的区间。在第 5.3 节四类边的定义里，区间包含关系已经把所有情况覆盖了。

flowchart LR
    B1["0( 1( 3( 2( 4( 5( 5) 4) 2) 3) 1) 0)"]
    B2["树边：区间嵌套且相邻"]
    B3["回边：后代区间含在祖先区间内"]
    B1 --> B2
    B1 --> B3

以后你会在很多高级图算法（Tarjan 求割点、Kosaraju 求强连通分量）里反复看到”区间""低链接值""最小发现时间”这些词，它们全部发源于今天这个简单的括号序列。

DFS 森林：不连通图的完整时间表

如果图不连通，外层循环会对每个连通块各发起一次 DFS，得到一片DFS 森林。时间戳照样全局递增，但不同树的区间彼此完全分离——因为它们之间没有任何访问关系。举个例子：图有两个连通块 {0, 1} 和 {2, 3}，从 0 和 2 分别发起 DFS：

graph LR
    subgraph T1["DFS 树 1"]
        A1["0（d=1, f=4）"] --> B1["1（d=2, f=3）"]
    end
    subgraph T2["DFS 树 2"]
        A2["2（d=5, f=8）"] --> B2["3（d=6, f=7）"]
    end

观察时间戳：第一棵树的区间 [1,4]、[2,3] 和第二棵树的 [5,8]、[6,7] 完全分离，互不包含。这正好对应”两个连通块之间没有任何边”的事实。所以时间戳不仅描述单棵 DFS 树，还描述整片森林的”时间切片”：每个连通块占一段连续的时间。

5.3 四类边：树边、前向边、回边、横叉边

有了 DFS 树和时间戳，我们可以把图里的每条边分门别类。以顶点 u 到顶点 v 的边为例：

树边（Tree Edge）：DFS 正是通过这条边递归进入 v 的，也就是 DFS 树里的边。特征：d[u] < d[v] < f[v] < f[u]，且 v 是 u 的直接孩子。

回边（Back Edge）：v 是 u 的祖先。也就是说，从后代有一条边连回祖先。无向图里，凡是没成为树边的边，都是回边。特征：d[v] < d[u] < f[u] < f[v]。回边是环的直接证据。

前向边（Forward Edge）：v 是 u 的后代，但不是直接孩子。有向图里可能出现这种情况：u 有一条边指向某个孙子，但 DFS 没走它。特征：d[u] < d[v] < f[v] < f[u] 且 v 不是 u 的孩子。

横叉边（Cross Edge）：u 和 v 没有任何祖先关系，各自在不同的子树里。特征：两个时间区间完全分离。

用一张示意图把这四类边画在一起（有向图）：

graph TD
    A["A d=1 f=8"]
    B["B d=2 f=7"]
    C["C d=3 f=6"]
    D["D d=4 f=5"]
    E["E d=9 f=10"]
    A ==>|"树边"| B
    B ==>|"树边"| C
    C ==>|"树边"| D
    C -.->|"回边到 A"| A
    A -.->|"前向边到 C"| C
    B -.->|"横叉边到 E"| E

直觉级理解就够了，先不深究：

• 回边 = 有环。无向图里有一条回边，就说明存在环；有向图里同理。反过来，如果 DFS 从头到尾没发现回边，图就是无环图。第 6 节环检测就是利用这个性质。
• 横叉边只在有向图里”真正出现”。无向图里一条边如果没被走成树边，两端的区间一定是嵌套的，所以只能是回边；横叉边是无向图不可能有的类别。
• 前向边比较”可有可无”。它存在说明图里有冗余的捷径，但对 DFS 的分析影响不大，很多教材干脆把它并进树边的讨论。

5.4 前序与后序：两个观察世界的窗口

第 2 节代码里有两个位置：前序位置（进入时）和后序位置（离开时）。现在配上时间戳，两个位置的意义更清楚了：

前序位置：顶点刚被发现，它的”势力范围”还没展开。此时适合做与”到达”相关的事：记录访问顺序、染色、计数、初始化。

后序位置：顶点的所有后代都处理完了，可以汇总信息。此时适合做与”完成”相关的事：把结果从子树向上传递、记录完成顺序、释放资源。

很多看似玄妙的算法，本质就是”把答案放在正确的窗口里”。举个经典例子：树的直径（最长路径长度）可以用后序位置自底向上合并；拓扑排序要按完成时间倒序输出（第 6 节会细讲）；求子树大小要把计数放在后序位置。记住这句话：前序是向下走时顺手记录，后序是向上走时汇总答案。

5.5 DFS 为什么是”万能脚手架”

BFS 擅长按层扩散，DFS 擅长”深入 + 回溯”，而”深入 + 回溯”恰好给了我们一种天然的递归分解能力：把问题拆成”处理当前顶点 + 递归处理子树 + 汇总”。很多图算法都是在 DFS 骨架上加一点料：

• 加一个计数器 → 连通分量
• 检查回边 → 环检测
• 后序位置记录 → 拓扑排序
• 在时间和反向图上各做一次 DFS → 强连通分量
• 维护路径栈 → 回溯法解迷宫、N 皇后
• 维护”最小发现时间” → 割点、桥（未来文章的伏笔）

DFS 就像一张可以无限挂载配件的通用底盘。下一节，我们先预览四个最经典的配件。

6 DFS 的应用预览：四个招牌

这一节只做”预览”，把四个应用讲出直觉和思路，具体的完整推导留给对应篇章。你不需要现在就全懂，只需要记住一句话：它们都是 DFS 骨架 + 一点额外信息。

6.1 连通分量：数一数图有几块

第 2 节我们写过的 dfsAll 已经能数连通分量：外层循环每发起一次 DFS，就覆盖一个全新的连通块。所以只要加一个计数器：

function countComponents(graph: number[][]): number {
  const visited: boolean[] = new Array(graph.length).fill(false);
  let count = 0;

  function visit(u: number): void {
    visited[u] = true;
    for (const v of graph[u]) if (!visited[v]) visit(v);
  }

  for (let u = 0; u < graph.length; u++) {
    if (!visited[u]) {
      count++;
      visit(u);
    }
  }
  return count;
}

原理极简：第一次 DFS 从某顶点出发，会把它所在的整个连通分量染遍；第二次从新起点出发，必然属于另一个分量。每次”发起新 DFS”都意味着发现新大陆。如果想顺便把每个顶点属于第几块记下来，就把 count 写进一个 component 数组。这也是并查集（树系列第 18 篇）之外的另一种连通性方案：DFS 在线（一次性全图）场景更简单，并查集则擅长动态加边。

图示：

graph LR
    subgraph C1["第 1 个连通分量"]
        A["A"] --- B["B"]
        B --- C["C"]
    end
    subgraph C2["第 2 个连通分量"]
        D["D"] --- E["E"]
    end
    subgraph C3["第 3 个连通分量"]
        F["F"]
    end

外层循环依次看到 A（发起第 1 次 DFS，染完 A、B、C）、D（第 2 次，染完 D、E）、F（第 3 次），答案 3。

6.2 环检测：发现回边就报警

无向图：DFS 过程中，如果发现一条边指向一个已访问且不是自己父节点的顶点，就说明存在回边，也就是有环。为什么排除父节点？因为无向图里父子和邻居互相连着，u 看到父亲 v 时，v 已访问是必然的，但这不构成环——那只是你刚刚走下来的那条边。真正构成环的，是通向”更早祖先”的边。

有向图：判断更简单，但需要区分”灰色”（正在栈中）和”黑色”（已完成）。只有指向灰色顶点的边才是回边；指向黑色顶点的边是横叉边或前向边，不算环。为什么？因为在有向图里，只有”栈中的祖先”才能和你共同构成一个圈。

flowchart LR
    A["A（灰色）"] --> B["B（灰色）"]
    B --> C["C（灰色）"]
    C -. "回边：指向灰色祖先 A" .-> A

实现时把 visited 升级成三态：0 = 未访问，1 = 访问中（灰色，在栈里），2 = 已完成（黑色）。递归进入时置 1，返回前置 2；遇到状态 1 的邻居就发现环。

用代码把无向图的环检测写全：

function hasCycleUndirected(graph: number[][]): boolean {
  const visited: boolean[] = new Array(graph.length).fill(false);

  function dfs(u: number, parent: number): boolean {
    visited[u] = true;
    for (const v of graph[u]) {
      if (v === parent) continue;      // 指向父亲的是树边，跳过
      if (visited[v]) return true;     // 指向已访问的"非父亲"= 回边 = 有环
      if (dfs(v, u)) return true;
    }
    return false;
  }

  for (let u = 0; u < graph.length; u++) {
    if (!visited[u] && dfs(u, -1)) return true;
  }
  return false;
}

有向图的环检测则完全依赖三态：

function hasCycleDirected(graph: number[][]): boolean {
  const color: number[] = new Array(graph.length).fill(0); // 0 白，1 灰，2 黑

  function dfs(u: number): boolean {
    color[u] = 1;
    for (const v of graph[u]) {
      if (color[v] === 1) return true;      // 灰 = 栈中祖先 = 有向回边
      if (color[v] === 0 && dfs(v)) return true;
    }
    color[u] = 2;
    return false;
  }

  for (let u = 0; u < graph.length; u++) {
    if (color[u] === 0 && dfs(u)) return true;
  }
  return false;
}

有向图为什么必须区分灰和黑？看一个反例：A → B，B → A 是有环的；但 A → B 和 C → B 无环。如果只用二态（未访问/已访问），从 A 出发访问 B 后标记，从 C 出发再访问 B 时只看到”已访问”，不会误报；可问题是：如果从 A 出发走 A → B，然后 B 的邻居 A 已访问，二态会误判成环——实际上这条边只是普通的”回到已完成顶点”，不是回边。只有灰色能区分”还在栈中”和”早已完成”，这就是三态存在的全部理由。

6.3 拓扑排序：按依赖顺序排队

拓扑排序解决的是”先修课”问题：有向无环图里，给所有顶点排一个顺序，使得每条边的起点都排在终点前面。DFS 给出的解法漂亮得惊人：按完成时间从大到小排序（或者说，按后序位置的逆序输出）。

直觉：后序位置意味着”我子树里的所有依赖都处理完了，我可以交卷了”。越晚完成的任务，依赖链越长，越应该排在前面。比如课程依赖图：A 依赖 B、C，B 依赖 D，DFS 完成顺序可能是 D、C、B、A，倒过来就是 A、B、C、D——每条依赖边都满足”先修在前”。

graph LR
    D["D 先修"] --> B["B"]
    C["C 先修"] --> A["A"]
    B --> A

细节留给第 7 篇，但请你记住这个”后序逆序”的招数，它是 DFS 最优雅的应用之一。顺带一提：如果拓扑排序过程中发现环，任务就无解了——这也把环检测和拓扑排序串在了一起。

再补一个直观例子。课程依赖：算法需要先修数据结构，数据结构需要先修编程基础；机器学习需要先修线性代数和算法。图如下：

graph LR
    P["编程基础"] --> D["数据结构"]
    D --> A["算法"]
    L["线性代数"] --> M["机器学习"]
    A --> M

DFS 从编程基础出发，一路钻到算法、机器学习，完成顺序大致是：机器学习（最深的先完成）、算法、线性代数、数据结构、编程基础。把它倒过来，就得到拓扑序：编程基础 → 数据结构 → 算法 → 线性代数 → 机器学习（线性代数也可以在算法之前，只要保证每条边起点在前即可）。注意拓扑序不唯一，任何满足”先修在前”的顺序都合法——这也是为什么不同教材给出的答案可能不同。

6.4 强连通分量：在有向图里找”互达集团”

有向图里，如果两个顶点能互相到达（u 能到 v，v 也能到 u），它们就属于同一个强连通分量。最有名的算法之一叫 Kosaraju，核心只有两步：

1. 在原图上做一次 DFS，记录每个顶点的完成时间；
2. 在反向图（所有边反向）上按完成时间从大到小的顺序做 DFS，每次 DFS 恰好扫出一个强连通分量。

为什么反向图这么神奇？直觉是这样的：完成时间晚的顶点，在原图里”地位更高”（能到达更多地方）；在反向图上从它出发，能反向追溯到的顶点，恰好都是能和它互相到达的。完整证明比较长，第 13 篇会给出。今天只需要记住：强连通分量 = 两次 DFS + 反向图。

graph LR
    subgraph SCC1["强连通分量 1"]
        A["A"] --> B["B"]
        B --> A
    end
    subgraph SCC2["强连通分量 2"]
        C["C"] --> D["D"]
        D --> C
    end
    A --> C
    B --> D

6.5 应用一览表

应用	DFS 骨架上的额外信息	关键位置	将在哪一篇详解
连通分量	计数器 + component 数组	前序/外层循环	本篇
环检测（无向）	排除父节点的回边判断	邻居检查时	第 6 篇
环检测（有向）	三态 visited	邻居检查时	第 6 篇
拓扑排序	后序顺序逆序	后序位置	第 7 篇
强连通分量	完成时间 + 反向图	两次 DFS	第 13 篇
割点 / 桥	最小发现时间 low	后序位置	后续文章

看到规律了吗？四个应用全都围绕两个核心概念打转：时间戳和后序位置。所以第 5 节绝不是闲笔，它是通往所有进阶算法的钥匙。

6.6 一个统摄全局的观察

把四个应用并排看，会发现一个隐藏的统一模式：它们都在问”DFS 能不能给我某种顺序或某种结构”。连通分量要的是”分组”，环检测要的是”回边”，拓扑排序要的是”后序逆序”，强连通分量要的是”两次 DFS 的完成顺序”。也就是说，DFS 不只是一个”走一遍”的算法，而是一个顺序生成器：它生成的发现顺序、完成顺序、树结构、时间区间，可以被不同算法各取所需。

这也是为什么面试官总爱问 DFS 的”前序和后序分别能干什么”——因为答案直接反映你是否理解 DFS 的信息结构。前序给你”到达顺序”，后序给你”完成顺序”，时间戳给你”区间关系”，DFS 树给你”祖先关系”。这四个信息，就是图论里很多经典算法的全部原料。

flowchart TD
    DFS["DFS 生成的信息"] --> S1["发现顺序"]
    DFS --> S2["完成顺序"]
    DFS --> S3["DFS 树 / 森林"]
    DFS --> S4["时间戳区间"]
    S1 --> A1["连通分量、染色"]
    S2 --> A2["拓扑排序、强连通分量"]
    S3 --> A3["祖先关系、子树"]
    S4 --> A4["回边判定、括号性质"]

7 BFS vs DFS：全面对比

7.1 数据结构：队列 vs 栈

BFS 用队列：先来先服务，先发现的顶点先被处理，于是访问一圈一圈向外扩。DFS 用栈（递归版由系统调用栈隐式提供）：后进先出，刚发现的顶点立刻优先处理，于是访问一路向深处扎。

这一个差异解释了几乎所有其他差异。队列的”排队”天然适合分层，栈的”压摞”天然适合回溯。如果你在写代码时忘了用哪个，就回忆两个词：队列管广度，栈管深度。

flowchart LR
    subgraph Q["BFS：队列（先进先出）"]
        direction LR
        Q1["队首出队"] --> Q2["下一圈顶点排队"]
    end
    subgraph S["DFS：栈（后进先出）"]
        direction LR
        S1["栈顶出栈"] --> S2["新发现的顶点立刻深入"]
    end

7.2 空间复杂度：队列宽，栈深

这是两者最反直觉的对比之一。

BFS 的空间主要花在队列上：最坏情况下，同一层的顶点几乎都在队列里。对一棵”扇出极大”的树（根有 n-1 个孩子），BFS 队列里会同时躺着 O(n) 个顶点；对一张稠密图，队列大小同样可能到 O(V)。

DFS 的空间主要花在栈上：最坏情况下，栈里是”当前路径上的顶点”，深度最多是 V。如果图是一条链，栈会一直长到 O(V)；但如果图是个”星形”（中心连所有叶子），DFS 的栈深度只有 O(1)——因为每钻一个叶子就立刻返回。

所以不能简单说”DFS 省空间”：BFS 的空间与”层宽”成正比，DFS 的空间与”路径深”成正比。选哪个要看图是宽还是深。一棵深度 1 万、每层 2 个节点的二叉树，BFS 队列最多几十个节点，DFS 栈却要 1 万层；反过来，一张深度只有 3、但每层有 1 万个节点的图，DFS 栈很小，BFS 队列却可能很大。

用表格总结：

维度	BFS	DFS
核心结构	队列	栈（或递归调用栈）
空间大小	与”一层最多多少个顶点”成正比	与”一条路最多多深”成正比
最坏空间	O(V)（稠密图/宽树）	O(V)（长链）
最优场景	浅而宽的图	深而窄的图

7.3 访问顺序：按层 vs 按路径

BFS 的访问顺序是”距离优先”：先访问距离起点 1 的所有顶点，再访问距离 2 的……因此 BFS 第一次碰到某个顶点时，走的一定是最短路径。DFS 的访问顺序是”深度优先”：先扎到一条路径的尽头，再回头走下一条；它第一次碰到某个顶点时，路径不一定最短，甚至可能很长。

用一张图演示。起点 S，目标 T，S 有两条路到 T：S → A → T（长度 2）和 S → B → C → D → T（长度 4）：

graph LR
    S["S"] --> A["A"] --> T["T"]
    S --> B["B"] --> C["C"] --> D["D"] --> T["T"]

BFS 一定会先扫到 A 层，再扫到 B 层，所以找到 T 时路径是 S → A → T。DFS 如果先走 B 分支，会一直钻到 D 才找到 T，路径长 4——虽然”找到即可”，但显然不是最短。这个例子说明：无权最短路径问题选 BFS，找路问题（找到就行）可以选 DFS。

7.4 适用场景：各有所长

BFS 的用武之地：

• 无权图的最短路径、最少步数、最少转换次数；
• 分层扩散类问题：多源感染、迷宫最短步数、单词接龙；
• 状态空间里”步数最少”的搜索（八数码、推箱子）；
• 需要”第几层”这种层级信息的场景（二叉树的层序遍历）。

DFS 的用武之地：

• 连通性、连通分量、染色问题；
• 环检测、拓扑排序、强连通分量等图论高级算法；
• 回溯/枚举类问题：走迷宫找任意一条路、N 皇后、子集组合排列；
• 需要”深度路径”或”祖先-后代关系”的场景；
• 图的剪枝搜索（深搜配合剪枝可以高效探索解空间）。

7.5 一张对比总表

对比项	BFS	DFS
中文名	广度优先搜索	深度优先搜索
核心数据结构	队列	栈（递归调用栈）
访问原则	先发现先处理（FIFO）	后进先出（LIFO）
访问顺序	按距离分层扩散	沿一条路走到底再回溯
能否保证无权最短路	能	不能
空间特征	与层宽成正比	与深度成正比
是否需要 visited	需要	需要
实现难度	低（循环 + 队列）	低（递归最简，迭代稍繁）
天然信息	距离、最短路径	DFS 树、时间戳、路径栈
典型应用	最短步数、层序、多源扩散	连通分量、环检测、拓扑、SCC、回溯
无向图找环	不直观	回边直接识别
结束时机	队列清空	栈清空 / 递归返回

最后补一句常见的面试感悟：BFS 和 DFS 不是竞争关系，而是互补关系。同一道题，BFS 给距离，DFS 给结构；很多难题要两者配合，比如先用 DFS 找出连通块，再对块内做 BFS 求最短路径。掌握两者的差异，才能在合适的场景选出合适的工具。

7.6 怎么选：一张决策流程图

面对一道图上的搜索题，可以用下面这张流程图快速定位工具：

flowchart TD
    Q1["问题关心最短步数 / 最少次数？"] -->|"是"| BFS["BFS：按层扩散，第一次到达即最短"]
    Q1 -->|"否"| Q2["关心连通性 / 结构 / 祖先关系？"]
    Q2 -->|"是"| DFS["DFS：DFS 树、时间戳、回边"]
    Q2 -->|"否"| Q3["需要枚举所有方案？"]
    Q3 -->|"是"| BACK["DFS + 回溯：选择、递归、撤销"]
    Q3 -->|"否"| EITHER["两者皆可，按实现难度选"]

当然，流程图只是第一层判断。实际工程里还有两个次要因素：图的形状（宽还是深）和问题的终止条件（找到一条路即可，还是必须保证最优）。把这些因素叠在一起，就是一次完整的算法选型。

7.7 三种经典面试追问

面试官检验你是否真懂 BFS/DFS 差异时，常追问这三个问题：

追问一：“DFS 能找到最短路径吗？” 答案：不能保证。DFS 找到的第一条路径只代表”存在一条路”，不代表最短。除非你枚举所有路径取最小值——那等于退化成搜索整棵路径树，指数级开销，不如直接用 BFS。

追问二：“BFS 的空间一定比 DFS 大吗？” 答案：不一定。两者最坏都是 O(V)，但实际开销取决于图的形状。宽而浅的图 BFS 费空间，深而窄的图 DFS 费空间。正确的说法是”队列大小与层宽相关，栈深度与路径深度相关”。

追问三：“visited 对 BFS 和 DFS 的作用一样吗？” 答案：机制上一样——都是防止重复访问；但细节不同。BFS 的 visited 在入队时标记（防止同一顶点被多次入队），DFS 在进入时标记（防止互相递归）。两者都不能等”处理完”再标记，理由类似：标记太晚，重复就发生了。

这三个追问背后其实是同一件事：不要背结论，要理解数据结构的时序。队列的时序决定 BFS 的分层，栈的时序决定 DFS 的深度，visited 的标记时机决定正确性，这三条线贯穿两篇的全部内容。

7.8 同一张图，两种遍历，两种故事

用一个具体例子把对比收尾。还是第 3 节那张六顶点图，起点 0，邻居顺序不变：

graph LR
    0["0"] --- 1["1"]
    0 --- 2["2"]
    1 --- 3["3"]
    2 --- 3["3"]
    2 --- 4["4"]
    3 --- 5["5"]
    4 --- 5["5"]

BFS 的输出（按层）：0 → 1 → 2 → 3 → 4 → 5。它像涟漪一样，先扫 0 的一层邻居 1、2，再扫 1、2 的邻居 3、4，最后扫到 5。DFS 的输出（第 3 节）：0 → 1 → 3 → 2 → 4 → 5。它先扎进 0 → 1 → 3 → 2 → 4 → 5 这条路径，再回头补漏。

两种顺序都是”合法的遍历”，但它们携带的信息完全不同：

输出顺序	蕴含的信息	直接可回答的问题
BFS：0,1,2,3,4,5	每个顶点在第几层	0 到 5 的最短步数（3）
DFS：0,1,3,2,4,5	每个顶点的父子关系	0 和 3 是不是祖先关系（是）

看 BFS 的顺序，你能立刻知道 0 → 5 最短 3 步；但看不出 1 和 3 的父子关系。看 DFS 的顺序，你知道 3 是 1 的孩子、2 是 3 的孩子；但说不出 0 → 5 的步数。BFS 回答”多远”，DFS 回答”多深”，这就是两种遍历各自的价值。题目问什么，就选对应的那个——这也是第 7.6 节决策流程图背后的全部逻辑。

8 典型问题：从”遍历”到”解决问题”

这一节我们把 DFS 用在两道非常经典的算法题上。两道题都很小，但足够展示 DFS 从”遍历工具”升级为”问题求解器”的完整路径。

8.1 岛屿数量：DFS 染色

题目背景：给定一个 m × n 的二维网格，‘1’ 表示陆地，‘0’ 表示海水。陆地上下左右相邻算同一座岛屿。问一共有几座岛屿。

这就是”连通分量计数”的二维版：把每个 ‘1’ 看作顶点，上下左右相邻的 ‘1’ 之间连边，数一数有几个连通块。DFS 的解法叫”染色法”：遇到一个没访问过的 ‘1’，就从它开始 DFS，把它所在整块陆地全部标记为已访问（或者直接改成 ‘0’，就地淹没），计数器加一。外层循环扫完整张网格，计数器的值就是岛屿数。

graph TD
    subgraph G1["网格"]
        direction LR
        C11["1"] --- C12["1"]
        C12 --- C13["1"]
        C21["1"] --- C31["1"]
        C13 --- C23["0"]
    end

DFS 的每一步就是”从当前格子向四个方向蔓延，遇到水或越界就回头”。访问标记直接改在原数组上，连 visited 数组都省了。代码：

function numIslands(grid: string[][]): number {
  const m = grid.length;
  const n = grid[0].length;
  let count = 0;

  function dfs(i: number, j: number): void {
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] === '0') return;
    grid[i][j] = '0';            // 淹没：标记已访问
    dfs(i - 1, j);
    dfs(i + 1, j);
    dfs(i, j - 1);
    dfs(i, j + 1);
  }

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === '1') {
        count++;
        dfs(i, j);               // 淹没整座岛
      }
    }
  }
  return count;
}

注意这里的 visited 标记时机：进入格子后立刻改成 ‘0’。这正是第 2 节”进入时标记”原则的体现——如果不立刻淹没，相邻格子之间会互相递归，栈就爆了。

把这道题的手算走查做一遍，巩固”染色”的感觉。假设网格是：

1 1 0 0
1 0 0 1
0 0 1 1

扫描顺序从左到右、从上到下。扫到 (0,0) 是 ‘1’，计数器变 1，DFS 从 (0,0) 出发：右走到 (0,1)，下走到 (1,0)，全部淹没，第一个连通块覆盖 (0,0)、(0,1)、(1,0)。继续扫描，(0,2)、(0,3)、(1,2) 都是 ‘0’，跳过；扫到 (1,3) 是 ‘1’，计数器变 2，DFS 淹没它自己（四个方向没有相邻陆地）。继续扫到 (2,2) 是 ‘1’，计数器变 3，DFS 淹没 (2,2) 和 (2,3)。最终答案是 3。

把三个连通块画出来：

graph LR
    subgraph I1["第 1 座岛"]
        G11["(0,0)"] --- G12["(0,1)"]
        G11 --- G13["(1,0)"]
    end
    subgraph I2["第 2 座岛"]
        G21["(1,3)"]
    end
    subgraph I3["第 3 座岛"]
        G31["(2,2)"] --- G32["(2,3)"]
    end

注意 (1,0) 和 (0,1) 并不相邻（对角线不算），所以它们属于同一座岛靠的是共同连到 (0,0)。这也提醒我们：题目说”上下左右相邻”时，对角线一律不算，写代码时只需要四个方向的递归，不要写八方向。

这道题还有一个经典变体：岛屿最大面积。只需在 DFS 里统计”淹没了几块陆地”并维护最大值。这也展示了 DFS 后序汇总的威力：每个格子把自己四个方向的面积加起来，再向上返回。

8.2 迷宫寻路：找到一条路就行

题目背景：给定一个迷宫（二维网格，0 可走、1 是墙），从入口出发，能否到达出口？输出一条可行路径。

这种”找到即可”的问题，DFS 是自然选择：从入口出发，按上右下左的顺序尝试，能走就走，走不通就回溯；一旦走到出口，立刻停下返回。由于 DFS 深入优先，它会很快扎到某个尽头；如果运气好，一条路直通出口，甚至不用探索整张图。

graph TD
    E["入口"] --> A["A"] --> B["B"]
    B --> C["C（死胡同）"]
    B --> D["D"]
    D --> X["出口"]

上面这条路 E → A → B → D → X 一次成功。如果 D 的方向选错了，先进了死胡同 C，DFS 会退回来再试 D——这就是回溯。回溯的代码形态很典型：进入递归前记录，递归返回后撤销。

function hasPath(maze: number[][], start: [number, number], end: [number, number]): boolean {
  const m = maze.length;
  const n = maze[0].length;
  const visited: boolean[][] = Array.from({ length: m }, () => new Array(n).fill(false));

  function dfs(i: number, j: number): boolean {
    if (i < 0 || i >= m || j < 0 || j >= n || maze[i][j] === 1 || visited[i][j]) {
      return false;
    }
    visited[i][j] = true;
    if (i === end[0] && j === end[1]) return true;   // 到达出口
    if (dfs(i - 1, j)) return true;
    if (dfs(i + 1, j)) return true;
    if (dfs(i, j - 1)) return true;
    if (dfs(i, j + 1)) return true;
    return false;
  }

  return dfs(start[0], start[1]);
}

如果题目要求”打印路径”，把 visited 改成”路径栈”，递归进入时压入当前格，找到出口时输出整条栈；注意回溯时要把走错的分支弹出，否则路径里会混入死胡同。

迷宫问题还有一个常见变体：统计从入口到出口一共有多少条不同的路径。做法是把”找到出口就返回”改成”找到出口就计数加一”，并且回溯时撤销 visited，让其他路径也能经过同一个格子：

function countPaths(maze: number[][], start: [number, number], end: [number, number]): number {
  const m = maze.length;
  const n = maze[0].length;
  const visited: boolean[][] = Array.from({ length: m }, () => new Array(n).fill(false));
  let count = 0;

  function dfs(i: number, j: number): void {
    if (i < 0 || i >= m || j < 0 || j >= n || maze[i][j] === 1 || visited[i][j]) return;
    if (i === end[0] && j === end[1]) {
      count++;
      return;
    }
    visited[i][j] = true;
    dfs(i - 1, j);
    dfs(i + 1, j);
    dfs(i, j - 1);
    dfs(i, j + 1);
    visited[i][j] = false;   // 回溯：撤销标记，允许其他路径使用
  }

  dfs(start[0], start[1]);
  return count;
}

注意这里 visited 的标记方式变了：进入时标记、离开时撤销。这正是回溯法与普通 DFS 的分水岭——普通 DFS 的 visited 是”永久签证”，回溯法的 visited 是”临时通行证”。前者保证每个顶点只走一次，后者保证每条路径都能走。代价是复杂度：路径计数可能是指数级的，所以这类题目通常规模很小（比如 n ≤ 10）。

8.3 回溯思想一句话

迷宫、N 皇后、数独、括号生成、排列组合……这些题的共同内核可以浓缩成一句话：做出选择 → 递归深入 → 若此路不通，撤销选择 → 尝试下一个选择。选择是”分支”，递归是”深入”，撤销是”回溯”。DFS 提供了这个框架，而”撤销”这一步正是回溯法区别于普通 DFS 的关键——普通 DFS 只标记”来过”，回溯法还要”还原现场”，好让后续分支看到干净的状态。

举一个 N 皇后的小例子：在棋盘第 row 行放皇后，如果和已放皇后冲突就换列；放满 row 行就找到一个解；递归返回后把皇后撤掉，继续试下一列。每一层递归对应一行，每一行有 n 个选择，DFS 在”选择树”里搜索，这就是回溯。

flowchart TD
    Root["第 0 行，放第 0 列"] --> A["第 1 行，试第 1 列（冲突，回溯）"]
    A --> B["第 1 行，试第 2 列（可行）"]
    B --> C["第 2 行，试第 3 列（可行）"]
    C --> D["第 3 行，无列可放，回溯"]
C --> E["第 3 行，换列可行 → 找到解"]

再看一个具体的 4×4 迷宫走查，体会”走错再回来”的节奏。入口在左上角 (0,0)，出口在右下角 (3,3)，墙用灰色标记：

flowchart TD
    M00["(0,0) 入口"] --> M01["(0,1)"]
    M01 --> M02["(0,2)"]
    M02 --> M12["(1,2)"]
    M12 --> M13["(1,3) 死胡同"]
    M12 --> M22["(2,2)"]
    M22 --> M23["(2,3)"]
    M23 --> M33["(3,3) 出口"]

假设 DFS 在每个格子按”上、右、下、左”的顺序尝试。从入口出发一路向右走到 (0,2)，向下到 (1,2)，先试 (1,3) 发现是死胡同（或者已访问），退回 (1,2) 再试 (2,2)，一路走到出口。整个过程中只有 (1,3) 这一步走错了路，其余都是直捣黄龙。如果题目要的是”所有路径”，DFS 会继续从出口往回撤，枚举其他走法；如果只是”找到一条”，到达出口立刻返回即可。

迷宫问题的两个常见变体顺便说清：最短步数要用 BFS（因为 DFS 找到的第一条路不保证最短）；存在路径且路径可以绕墙要用 DFS 加 visited（防止在环上打转）。一个容易忽略的细节：有些迷宫题允许重复经过格子（比如收集所有金币），此时 visited 的规则要按题目重新设计，不能无脑套模板。

8.4 从两道题看 DFS 的三种形态

岛屿数量、迷宫寻路、N 皇后，正好对应 DFS 的三种形态：

1. 遍历型（岛屿数量）：把整张图扫一遍，统计结构信息，visited 只标记不撤销；
2. 搜索型（迷宫寻路）：找一条满足条件的路径，找到即可提前返回；
3. 回溯型（N 皇后）：枚举所有可行方案，需要撤销选择、还原现场。

三种形态的代码骨架几乎一样，区别只在”返回后是否恢复状态”和”找到答案是否立即停止”。理解了这三层，你就理解了 DFS 在算法题里的绝大多数用法。

最后用一张小表收束三种形态，方便做题时对照：

形态	visited 是否撤销	找到答案是否停止	典型题
遍历型	否	遍历完才停	岛屿数量、连通分量
搜索型	否	找到即停	迷宫判路、可达性
回溯型	是	枚举完才停	N 皇后、排列组合、数独

做题的第一步不是写代码，而是先问自己三个问题：这是”走一遍”还是”找答案”？找到一条路够不够？一条路径能不能复用同一个顶点？三个问题的答案组合，就决定了该用哪种形态、visited 要不要撤销。把这一步想清楚，很多题根本不用试错。

8.5 复杂度再论：为什么是 O(V + E)？

DFS 的时间复杂度 O(V + E) 值得展开说清楚，因为它依赖两个前提：

第一，每个顶点只被”进入”一次。visited 在进入时标记，保证不会出现”同一个顶点被多条路径重复递归”的情况。所以 visit 函数总共执行 V 次。

第二，每条边只被”检查”有限次。在邻接表实现里，顶点 u 被访问（递归）时会把 graph[u] 整个扫一遍。每个顶点只扫一次自己的邻居表，所以总共扫描的次数是所有邻居表的长度之和：无向图是 2E，有向图是 E。常数 2 不影响复杂度，统一记 O(E)。

于是总时间 = 顶点处理（O(V)）+ 邻居扫描（O(E)）= O(V + E)。如果换成邻接矩阵，扫描一个顶点要遍历整行（O(V)），总时间变成 O(V²)，这正是第 3 篇强调”稀疏图用邻接表”的原因之一。

空间复杂度分解：

部分	大小	说明
visited 数组	O(V)	每个顶点一个布尔值
递归调用栈 / 显式栈	O(V)	最坏是一条链，深度 V
前序/后序数组（可选）	O(V)	需要时间戳时才开
邻接表本身	O(V + E)	图的存储，不算算法额外空间

所以 DFS 的额外空间是 O(V)。初学者常犯的错误是以为栈深度恒等于 V，实际上一棵平衡树的 DFS 栈深只有树高 O(log V)；但上界必须按最坏情况 O(V) 分析。

8.6 工程里的 DFS：别忘了几件小事

在真实工程里用 DFS，还有几件容易忽略的小事：

第一，自环和重边。自环（u 连 u）在无向图环检测里会立刻命中”已访问非父亲”；重边（两条 u-v 边）会让”跳过父亲”的逻辑失灵——第二条 u-v 边会误判成环。工程里要么建图时去重，要么环检测时把”父节点”扩展成”父节点 + 已经走过的边数”。

第二，超大图与递归栈溢出。10 万级别的链状图足以让很多语言的默认递归栈崩溃。工程上要么提高栈限制（某些语言支持），要么直接用迭代版。这提醒我们：递归版适合理解和中小规模数据，生产环境遇到深图要果断换栈。

第三，visited 的空间优化。有时可以借用原数据本身当标记：岛屿问题把 ‘1’ 改成 ‘0’；棋盘问题可以把已访问格子改成墙。这样省掉一个同尺寸数组，在小内存场景很有用，但要记得原数据被破坏，需要副本时另说。

第四，避免闭包变量陷阱。递归闭包共享 visited、order 等外层变量，一般没问题；但如果把 visited 当参数传来传去，要小心引用共享导致状态错乱。用类成员或模块级变量管理状态，是最省心的做法。

这些细节不会出现在教科书的主线里，但往往是线上事故和面试加分项的分水岭。

9 DFS 要点速查表

把本篇最重要的知识点收进一张表：

主题	要点
核心思想	一条路走到黑，走不动就回头；回头后继续试未走过的分支
与树 DFS 的关系	图 DFS = 树 DFS + visited
visited 标记时机	进入顶点时立刻标记；绝不能等到访问结束后才标记
visited 三态	白 = 未访问，灰 = 在递归栈中，黑 = 已完成；有向图判环用灰
递归实现	函数进入标记 → 前序操作 → 递归邻居 → 后序操作 → 返回
迭代实现	显式栈；朴素版与递归版顺序可能不同；反向压栈可恢复顺序
空间复杂度	栈深度 O(V)，最坏一条链；比 BFS 更省的情况是”深而窄”的图
时间复杂度	O(V + E)（邻接表），每个顶点进一次、每条边查一次
DFS 树	被递归走到的边构成树；树边 = 递归调用关系
时间戳	发现时间 d、完成时间 f；区间要么嵌套要么分离（括号性质）
四类边	树边、回边（有环）、前向边、横叉边
应用	连通分量、环检测、拓扑排序、强连通分量、割点桥、回溯搜索
与 BFS 差异	队列 vs 栈；按层 vs 按深；BFS 保最短，DFS 保结构
回溯法	选择 → 递归 → 撤销 → 下一个选择；visited 需要”撤销”
回溯一句话	选择 → 递归 → 撤销 → 下一个选择

这张表不是用来背的，而是用来自检的：随便指一行，如果你能用自己的话讲出背后的例子和原因，说明真的掌握了；如果只能复述句子，建议回到对应小节再看一遍。算法学习的检验标准从来不是”记得住”，而是”讲得清”。

10 自测题

11 下一篇预告

到此，图遍历的两大主角——BFS 和 DFS——都已经登场了。但”遍历”本身不是目的，它是手段。第 4 篇我们把 BFS 用在了最短步数上，这一篇又把 DFS 用在了连通分量和环检测上，但这些都还只是开胃菜。

下一篇《图系列第 6 篇：BFS/DFS 的应用》会把这两把刀磨得更利：用 BFS 解决多源扩散、单词接龙、状态空间搜索；用 DFS 解决环检测的完整实现、拓扑排序的两种写法、二分图判定；还会介绍”染色法”这个在面试里出现频率极高的套路。到时候你会发现，第 4 篇和第 5 篇打下的地基，终于要盖出第一栋高楼了。

记得把这一篇的速查表收藏好——下一篇文章里，我们会频繁引用”时间戳""回边""后序位置”这些概念。如果哪里还觉得模糊，回头再看一遍手算走查那一节，把递归调用栈的六帧图画一遍，一切都会清晰起来。

在告别之前，给你留一个”复习动作清单”：

1. 不看文章，手写递归版 DFS，并解释为什么 visited 必须进入时标记；
2. 在纸上把第 3 节那张六顶点图再走一遍，画出调用栈的六帧；
3. 用一句话向朋友解释 BFS 和 DFS 的区别（说不出来就是还没懂）；
4. 打开可视化实验室，分别用 DFS 和 BFS 跑同一张图，观察两种动画的差异；
5. 独立写出岛屿数量，再改造成岛屿最大面积。

五个动作做完，本篇的内容就真正属于你了。算法学习的秘密不在于读了多少遍，而在于动手画了多少遍、写了多少遍。

我们下一篇见。