深度优先搜索

深度优先搜索（Depth-First Search，DFS）是图与隐式状态空间遍历的最自然范式。想象你站在迷宫入口，眼前的岔路通向未知。最直觉的走法是：右手扶墙，遇岔路先挑一条往下走，走到死胡同就退回上一个岔口换路–这套「一条路走到黑、走不通就回退」的策略，正是 DFS 的精神。它和人类走迷宫的行为高度一致，也因此成为最容易「想得到」的搜索算法。

DFS 的适用面远不止迷宫。判断地图里有几个连通区域、有向图是否存在循环依赖、表达式树如何求值、数独如何被搜出解、网格里有几座岛屿–这些问题底层都共享同一种「深入-回退」的搜索骨架。它既是独立的搜索范式，又是回溯、拓扑排序、Tarjan 割点/桥/强连通分量、迭代加深等一大类算法的「底层引擎」。本文从迷宫直觉出发，讲透递归调用栈为何天然提供回退机制，再逐步展开树的前中后序、图的连通分量与环检测、拓扑排序、Tarjan 算法、网格 flood fill、剪枝与迭代加深，并在末尾点明它与回溯、BFS、DP 的分工边界。

核心思想与正确性直觉

DFS 的核心可以用一句话概括：沿一条未访问的边深入到底，无路可走时回退到最近的有未访问邻居的祖先，直到所有可达点都被访问。这里的「回退到最近的祖先」是关键–它不是随机跳转，而是严格按进入的逆序退回。

递归调用栈就是回退栈

为什么 DFS 的代码如此简洁？因为系统调用栈天然提供了回退机制。每次 dfs(u) 调用时，u 被压入调用栈；当 u 的所有邻居都处理完毕、函数返回时，u 自动弹出，控制权回到调用者（父节点）。这意味着我们不需要显式维护「从哪里来」的父指针–栈结构本身记住了来路。

调用栈剖面 (DFS 从节点 1 深探):

压栈过程:
  [1] -> [1,2] -> [1,2,3] -> [1,2,3,6]
                           -> [1,2,3,6,5]
                             -> [1,2,3,6,5,4]  ← 最深处

弹栈过程 (4 无未访问邻居):
  [1,2,3,6,5,4]
  -> [1,2,3,6,5]    4 弹出
  -> [1,2,3,6]      5 弹出
  -> ...            逐层退回

栈底 = 起点, 栈顶 = 当前深探端点
"无路可走" = 栈顶无未访问邻居 -> 弹栈回退

树的前序遍历（先访问根，再递归左右子树）就是无环图上的 DFS。DFS 是前序遍历在一般图上的推广：图可能有环，所以多了一个 visited 数组防重复进入。树形 DP、表达式求值等「树上 DFS」问题都是前序/后序遍历的自然应用。

正确性：为何能遍历到所有可达点

DFS 的完备性可以用反证法说明。设起点为 $s$，假设存在某个从 $s$ 可达的节点 $v$ 未被 DFS 访问。由于 $v$ 可达，$s$ 到 $v$ 存在一条路径 $s = u_0, u_1, \dots, u_k = v$。沿这条路径看，$u_0 = s$ 被访问了（DFS 的起点），$u_k = v$ 未被访问，因此路径上必存在某条边 $(u_i, u_{i+1})$ 其中 $u_i$ 已访问而 $u_{i+1}$ 未访问。但 DFS 在处理 $u_i$ 时会枚举其所有邻居，遇到未访问的 $u_{i+1}$ 必然递归进入–矛盾。故所有从 $s$ 可达的点必被访问。这一完备性与 BFS 相同，差异只在访问顺序与空间特征。

「深入到底再回退」的触发时机也很明确：当前节点无任何未访问邻居时返回（弹栈回到父节点）。这一条件保证了 DFS 不会在还有未探索分支时提前回头。

DFS 树与四类边

DFS 走过的「树边」（首次访问某节点时经过的边）构成原图的一棵生成树（或生成森林，若图不连通）。在这棵 DFS 树的视角下，原图的边可分为四类：

• 树边（tree edge）：DFS 树的边，指向首次访问的节点。
• 回边（back edge）：指向 DFS 树中某个祖先节点的边（非树边）。回边意味着环。
• 前向边（forward edge）：指向 DFS 树中某个后代节点的边（非树边）。仅在有向图中出现。
• 横叉边（cross edge）：既非祖先也非后代的边。仅在有向图中出现。

无向图只有树边和回边两类–这是无向图环检测比有向图简单的原因。四类边的区分是环检测、拓扑排序、Tarjan 算法的基础。

下面用一张 6 节点无向图展示 DFS 树与回边。每点标注 [enter, leave] 时间戳（进入与离开的顺序号）：

无向图 G (2×3 网格):       DFS 生成树 (从 1 出发):

  1──2──3                   1 [1,12]
  │  │  │                   │
  4──5──6                   2 [2,11]
                             │
                             3 [3,10]
                               │
                               6 [4,9]
                                 │
                                 5 [5,8]
                                   │
                                   4 [6,7]

  树边 (实线): 1-2, 2-3, 3-6, 6-5, 5-4
  回边 (虚线): 5-2, 4-1  ← 指向祖先, 构成环

DFS 树是一条链 1->2->3->6->5->4，两条回边各构成一个环。时间戳 enter/leave 是首次访问与处理完子树返回的顺序；子树中所有节点的 [enter, leave] 区间都包含在根节点的区间内，这一性质是 Tarjan 算法与子树查询的基础。

两种实现：递归与显式栈迭代

DFS 有两种等价的实现方式：递归与显式栈迭代。递归版借用系统调用栈，代码最贴近思维；迭代版自己维护一个栈，能规避栈溢出并精确控制访问顺序。

递归版

#include <vector>

void dfs(int u, const std::vector<std::vector<int>>& adj,
         std::vector<bool>& vis) {
  vis[u] = true;            // 进入节点: 立即标记
  // 前序动作写在这里 (如收集路径、更新答案)
  for (int v : adj[u]) {
    if (!vis[v]) dfs(v, adj, vis);
  }
  // 后序动作写在这里 (如拓扑逆后序、子树聚合)
}

代码极简：标记当前节点、遍历邻居、递归。前序动作（进入节点时做）与后序动作（离开节点时做）是两个天然的「可插拔点」–后续所有应用都在这两处填内容。主函数 for i in 0..n: if !vis[i] then dfs(i) 覆盖多连通块，下一节模板会给出完整写法。

显式栈迭代版

迭代版用一个显式栈模拟递归栈。核心循环：弹栈、若未访问则标记、压入所有未访问邻居。

#include <vector>
#include <stack>

void dfsIter(int start, int n,
             const std::vector<std::vector<int>>& adj) {
  std::vector<bool> vis(n, false);
  std::stack<int> stk;
  stk.push(start);
  vis[start] = true;            // 入栈即标记

  while (!stk.empty()) {
    int u = stk.top();
    stk.pop();
    // 处理 u (前序动作)
    for (int i = (int)adj[u].size() - 1; i >= 0; --i) {
      int v = adj[u][i];
      if (!vis[v]) {
        vis[v] = true;          // 入栈即标记, 避免重复入栈
        stk.push(v);
      }
    }
  }
}

等价性与标记时机

两种实现等价，但有一个常被忽视的差异：标记时机。

• 入栈即标记（上方写法）：节点压入栈时立刻标记 visited，后续不会被重复压入。空间最优，最推荐。代价是为复现递归访问顺序，邻居需逆序压栈（后访问的先压入，弹栈时才先出来）。
• 弹栈才标记：节点弹出时才标记。同一节点可能被多个前驱先后压入，导致栈膨胀，极端情况下（如完全图）栈中同时存在 $O(E)$ 个重复节点。

何时必须用迭代

三种场景下递归版会出问题：

1. 递归深度过大：链状图 $n = 10^5 \sim 10^6$ 时，递归深度等于链长，远超默认线程栈（Linux 默认 8MB，每帧几十到几百字节，约能支撑 $10^5$ 级别）。需改迭代或手动开大栈。
2. 需精确控制遍历顺序：如求字典序最小的路径，迭代版可以精确调整压栈顺序。
3. 运行环境限制递归深度：某些在线判题平台或嵌入式环境对栈深度有硬限制。

迭代 DFS 的「前序」容易写（弹栈时处理即可），但「后序」较难–需要额外标记「子节点是否已处理完毕」，或用双栈/颜色标记法。这也是为什么拓扑排序、Tarjan 等依赖后序的算法通常仍用递归实现（在栈深度允许的前提下）。

通用 DFS 模板

把两种最常见的形态–图（邻接表）与网格（方向数组）–提取成模板，后续所有应用都在此基础上填内容。

图 DFS 模板

#include <vector>

// 图 DFS 模板: 邻接表 + visited
// 复杂度 O(V + E), 每条边至多被枚举两次
void dfs(int u,
         const std::vector<std::vector<int>>& adj,
         std::vector<bool>& vis) {
  vis[u] = true;
  for (int v : adj[u]) {
    if (!vis[v]) {
      dfs(v, adj, vis);
    }
  }
}

// 主函数: 遍历所有连通块
int countComponents(int n,
    const std::vector<std::vector<int>>& adj) {
  std::vector<bool> vis(n, false);
  int cnt = 0;
  for (int i = 0; i < n; ++i) {
    if (!vis[i]) {
      dfs(i, adj, vis);
      ++cnt;               // 每启动一次 dfs 多一个连通块
    }
  }
  return cnt;
}

主循环 for i in 0..n: if !vis[i] then dfs(i) 是多连通块的关键–漏掉它只会遍历起点所在的连通块。参数传递上，adj 与 vis 用引用避免拷贝；坐标、计数器按需传值或传引用。

网格 DFS 模板

#include <vector>

// 方向数组: 右、左、下、上
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

void dfsGrid(int x, int y,
             std::vector<std::vector<char>>& board) {
  int m = board.size(), n = board[0].size();
  if (x < 0 || x >= m || y < 0 || y >= n) return;
  if (board[x][y] == '#') return;     // 已访问或不可走

  board[x][y] = '#';                   // 原地标记: 省 visited
  for (int i = 0; i < 4; ++i) {
    dfsGrid(x + dx[i], y + dy[i], board);
  }
  // 求所有解时需恢复: board[x][y] = old
  // 求一解或连通块标记时无需恢复
}

网格是「伪装成矩阵的图」：每格是一个节点，上下左右四邻接就是边。方向数组 dx/dy 是网格题的通用工具–八连通再加四对角 (-1,-1),(-1,1),(1,-1),(1,1) 即可。visited 有两种实现：通用 bool 数组，或网格题常用的原地修改（置 '#' 或异或），后者省去额外空间。

模板的四个可插拔点

所有 DFS 应用都在模板的四个位置填内容：

插点	时机	典型用途
前序动作	进入节点时	收集路径、更新全局答案、染色
后序动作	离开节点时	拓扑逆后序、子树大小聚合、Tarjan 涂黑
剪枝条件	枚举邻居时	越界/已访问/不匹配则跳过
答案收集	视问题而定	叶子收集（排列）或节点收集（子集）

后文每一节，本质上都是在回答「这四个插点填什么」。

树的 DFS

树是无环图，DFS 在树上即前序、中序、后序遍历。无需 visited（树无环），只需传 parent 参数避免回头。三种序的语义差异是本节重点。

前序（根左右）

struct TreeNode {        // 二叉树节点
  int val;
  TreeNode* left;
  TreeNode* right;
};
inline void visit(TreeNode*) {}  // 占位: 实际按需实现
void preorder(TreeNode* root) {
  if (!root) return;
  visit(root);              // 进入节点时做事
  preorder(root->left);
  preorder(root->right);
}

前序适合自顶向下传递信息：父节点信息已就绪，可以在「进入子节点前」把信息传下去。典型应用有路径前缀和、路径拼字符串、树的序列化（LeetCode 297）。

中序（左根右）

void inorder(TreeNode* root) {
  if (!root) return;
  inorder(root->left);
  visit(root);              // 左子树处理完再访问根
  inorder(root->right);
}

中序的标志应用是二叉搜索树（BST）：BST 的中序遍历得到升序序列。由此衍生出 BST 合法性验证、第 $k$ 小元素、最近公共祖先等问题。

后序（左右根）

void postorder(TreeNode* root) {
  if (!root) return;
  postorder(root->left);
  postorder(root->right);
  visit(root);              // 子树都处理完再访问根
}

后序适合自底向上聚合子树信息：离开节点时，左右子树的信息已齐备，可以合并到根。这是表达式求值、子树统计、树形 DP 的底层操作。树形 DP（如「没有上司的舞会」「树的直径」）的完整讲解见 动态规划 树形 DP 节。

应用一：表达式树求值

表达式树的每个内部节点是运算符，叶子是操作数。后序求值：先递归算出左右子树的值，再按根节点的运算符合并。

#include <string>

struct Node {
  bool isOp;              // true=运算符, false=操作数
  char op;                // '+','-','*','/'
  int val;                // 叶子的数值
  Node* left;
  Node* right;
};

int eval(Node* root) {
  if (!root->isOp) return root->val;    // 叶子直接返回
  int l = eval(root->left);             // 先算左子树
  int r = eval(root->right);            // 再算右子树
  switch (root->op) {                   // 按根运算符合并
    case '+': return l + r;
    case '-': return l - r;
    case '*': return l * r;
    case '/': return l / r;
  }
  return 0;
}

这是后序「自底向上聚合」的样板：子树的值先算好，父节点只需做一次合并。子树大小统计 size[u] = 1 + Σ size[child] 同理，是树链剖分与树形 DP 的底层操作。N 叉树的后序同理：for child in children: postorder(child) 先递归所有子节点，最后访问根。

应用二：子树大小统计

子树大小是后序聚合的最简形式：进入节点时不做事，递归完所有子节点后，把自己的 size 设为 1 + Σ size[child]。这一操作是树链剖分（重链/轻链划分依赖 size）、树形 DP（如树上背包按子树大小合并）的底层基础。树的直径也可用后序树形 DP 聚合：维护每个节点向子树方向的最长链与次长链，经过该节点的最长路径即为两者之和，全局取最大。

前序 vs 后序的本质

• 前序是「进入节点时做事」：此时父信息已就绪（自顶向下），适合传递。
• 后序是「离开节点时做事」：此时子树信息已齐备（自底向上），适合聚合。

判断用哪种序，只需问一个问题：当前节点需要的信息来自父节点还是子节点？ 来自父节点用前序，来自子节点用后序。

图的 DFS 应用：连通分量与环检测

连通分量

连通分量是 DFS 最直接的应用：主循环对每个未访问点启动一次 DFS，启动次数即为连通块数。上一节的 countComponents 模板已给出完整代码。

对于动态的「合并 + 查询」连通性场景（如不断添加边并询问两点是否连通），并查集更合适；DFS 适合静态图的一次性分析。两者的分工对照见 并查集。

无向图环检测

无向图判环只需在 DFS 中传一个 parent 参数：遍历邻居 v 时，若 v 已访问且 v != parent，则发现回边，存在环。

#include <vector>

bool hasCycleUndirected(int u, int parent,
    const std::vector<std::vector<int>>& adj,
    std::vector<bool>& vis) {
  vis[u] = true;
  for (int v : adj[u]) {
    if (!vis[v]) {
      if (hasCycleUndirected(v, u, adj, vis))
        return true;
    } else if (v != parent) {
      return true;          // 回边: v 已访问且非父节点
    }
  }
  return false;
}

重边陷阱：若两点间有两条平行边，v != parent 会误判为环（实际上 v 是父节点，只是有重边）。正确做法是传「父边编号」而非父节点，遇到同一条边时跳过。这一技巧在 Tarjan 求桥时也会用到。

有向图环检测：三色标记法

有向图的环检测更微妙。无向图的 parent 判断在这里失效–有向边是单向的，「已访问」的节点可能是祖先（构成环）也可能是不相干的已处理节点（横叉边，不构成环）。三色标记法解决了这个问题：

• 白色（0）：未访问。
• 灰色（1）：在当前递归栈中（即 DFS 路径上的祖先）。
• 黑色（2）：已完全处理（子树已遍历完毕）。

#include <vector>

// 三色标记: 0=白, 1=灰, 2=黑
bool hasCycle(int u,
    const std::vector<std::vector<int>>& adj,
    std::vector<int>& color) {
  color[u] = 1;                 // 涂灰: 进入递归栈
  for (int v : adj[u]) {
    if (color[v] == 0) {
      if (hasCycle(v, adj, color))
        return true;
    } else if (color[v] == 1) {
      return true;              // 遇灰 = 回边 = 环
    }
    // color[v]==2 (黑) 则跳过, 已处理完毕
  }
  color[u] = 2;                 // 涂黑: 子树处理完
  return false;
}

bool canFinish(int n,
    std::vector<std::vector<int>>& adj) {
  std::vector<int> color(n, 0);
  for (int i = 0; i < n; ++i) {
    if (color[i] == 0) {
      if (hasCycle(i, adj, color))
        return false;           // 有环, 无法完成
    }
  }
  return true;
}

三色标记的本质：灰色节点代表「当前 DFS 路径上的祖先」。遇到灰色节点意味着找到了一条从当前节点指向祖先的回边–这正是环的定义。返回前必须涂黑，否则后续从其他路径到达该节点时会误判为环。

三色标记过程示意：

有向图: A -> B -> C -> D, D -> B (回边)

步骤:
  1. dfs(A): A 灰, 栈=[A]
  2.   dfs(B): B 灰, 栈=[A,B]
  3.     dfs(C): C 灰, 栈=[A,B,C]
  4.       dfs(D): D 灰, 栈=[A,B,C,D]
  5.         D 的邻居 B 是灰色 -> 回边! 有环
             (B 在当前递归栈中 = 祖先)

涂黑时机: 递归返回前涂黑
黑节点 = 已完全处理, 再遇到不是环

应用：课程表（LeetCode 207）。$n$ 门课，先修关系构成有向图。能完成所有课程等价于图无环。上方的 canFinish 即为完整解法，复杂度 $O(V + E)$。

二分图判定（染色法）

DFS 染色是二分图判定的基础范式：对每个未染色节点 DFS，染成与父节点相反的颜色，若邻居已染色且与当前同色则非二分图。这本质上是 DFS 在「前序动作」处填入「染色」的模板应用，此处不展开代码。

图的 DFS 应用：拓扑排序

拓扑排序把有向无环图（DAG）的节点排成线性序列，使每条有向边 $(u, v)$ 中 $u$ 排在 $v$ 前面。它是编译依赖排序、任务调度的数学基础。DFS 实现拓扑排序的核心观察是：DFS 完成一个节点（涂黑）时，它依赖的节点要么已完成、要么仍在栈中–后序的逆序使「被依赖者排在前面」。

算法

在三色标记框架上加一个栈：节点涂黑时压入栈。最终栈顶到栈底即为拓扑序（逆后序）。

#include <vector>
#include <algorithm>

bool topoDfs(int u,
    const std::vector<std::vector<int>>& adj,
    std::vector<int>& color,
    std::vector<int>& order) {
  color[u] = 1;                  // 涂灰
  for (int v : adj[u]) {
    if (color[v] == 0) {
      if (!topoDfs(v, adj, color, order))
        return false;            // 有环
    } else if (color[v] == 1) {
      return false;              // 回边 = 环, 无拓扑序
    }
  }
  color[u] = 2;                  // 涂黑
  order.push_back(u);            // 后序: 涂黑时记录
  return true;
}

// 返回拓扑序 (已逆后序), 有环则返回空
std::vector<int> findOrder(int n,
    std::vector<std::vector<int>>& adj) {
  std::vector<int> color(n, 0);
  std::vector<int> order;
  for (int i = 0; i < n; ++i) {
    if (color[i] == 0) {
      if (!topoDfs(i, adj, color, order))
        return {};               // 有环
    }
  }
  std::reverse(order.begin(), order.end());
  return order;                  // 逆后序 = 拓扑序
}

为什么是「逆后序」而非「后序」。后序按完成顺序 push_back，最早完成的无依赖叶子排在最前。但拓扑序要求「指向别人的节点排前」–一个节点越晚涂黑，说明它越靠近 DFS 树的根、被依赖得越多，应排越前。reverse 把最晚涂黑的翻到最前，正是所需的。

与 Kahn 入度法对比

拓扑排序有两大实现：

维度	DFS 逆后序	Kahn 入度法
数据结构	递归栈 + 颜色数组	入度数组 + 队列
环检测	遇灰即环	队列空时仍有节点即环
字典序最小	不天然支持	用优先队列即可
代码紧凑性	与环检测合并，一行递归	需维护入度

Kahn 按入度做 BFS（每次取入度为 0 的节点入队），直观且易输出字典序最小拓扑序。DFS 逆后序的优势是与环检测天然合并、代码紧凑。课程表 II（LeetCode 210） 要求输出拓扑序，上方 findOrder 即为完整解法，复杂度 $O(V + E)$。应用场景还包括编译依赖顺序（make/cargo 的构建顺序）、任务调度等。

图的 DFS 应用：Tarjan 算法（割点、桥、SCC）

Tarjan 算法用 DFS 的时间戳 dfn 与 low 值，在一次 DFS 内求出无向图的割点、桥与有向图的强连通分量，是 DFS 的高阶武器。

dfn 与 low

• dfn[u]（Discovery Function Number）：节点 $u$ 被首次访问的时间戳，即 DFS 进入顺序。
• low[u]：$u$ 或 $u$ 的子树经至多一条回边能到达的最早祖先的 dfn。

low 的更新规则是 Tarjan 的核心，也是最容易出错的地方：

• 树边 $(u, v)$：low[u] = min(low[u], low[v])。子树能到达的最早祖先也是 $u$ 能间接到达的。
• 回边 $(u, v)$（$v$ 在栈中/已访问且是祖先）：low[u] = min(low[u], dfn[v])。注意是 dfn[v] 而非 low[v]。
• 横叉边/前向边（有向图）：不更新。这是高频低级错误。

为什么回边用 dfn[v] 而非 low[v]？因为回边只允许「经至多一条回边」到达 $v$ 本身，不应继承 $v$ 经其他回边到达的更早祖先。在无向图中没有横叉边/前向边，这一区分不那么关键；但有向图中用错会导致 low 值被错误地拉低。

割点判定

割点（articulation point）是删除后会使图不连通的节点。

• 根节点：若 DFS 树根有 $\ge 2$ 个树子节点，则根是割点（删根后子树间断开）。
• 非根节点 $u$：若存在树子节点 $v$ 使 low[v] >= dfn[u]，则 $u$ 是割点。含义是 $v$ 的子树无法绕过 $u$ 到达 $u$ 的上方，删 $u$ 后 $v$ 子树与上方断开。

桥判定

桥（bridge）是删除后使图不连通的边。边 $(u, v)$ 为树边且 low[v] > dfn[u]（严格大于），则 $(u, v)$ 是桥。> 而非 >=：若 low[v] == dfn[u]，说明 $v$ 子树能到达 $u$ 本身（经回边），删 $(u,v)$ 后 $v$ 子树仍与 $u$ 相连，不构成桥。

#include <vector>
#include <algorithm>

struct TarjanUndirected {
  int timer = 0;
  std::vector<int> dfn, low;
  std::vector<bool> isCut;       // 割点
  std::vector<std::pair<int,int>> bridges;

  void dfs(int u, int parentEdgeId,
      const std::vector<std::vector<std::pair<int,int>>>& adj) {
    dfn[u] = low[u] = ++timer;
    int childCount = 0;          // 根节点的树子节点数
    bool isRoot = (parentEdgeId == -1);
    for (auto& [v, eid] : adj[u]) {
      if (eid == parentEdgeId) continue;  // 跳过父边
      if (dfn[v] == 0) {        // 树边
        dfs(v, eid, adj);
        low[u] = std::min(low[u], low[v]);
        ++childCount;
        if (!isRoot && low[v] >= dfn[u])
          isCut[u] = true;      // 非根割点
        if (low[v] > dfn[u])
          bridges.push_back({u, v});
      } else if (dfn[v] < dfn[u]) {
        // 回边 (v 已访问且是祖先)
        low[u] = std::min(low[u], dfn[v]);
      }
    }
    if (isRoot && childCount >= 2)
      isCut[u] = true;          // 根割点
  }

  void run(int n,
      const std::vector<std::vector<std::pair<int,int>>>& adj) {
    dfn.assign(n, 0);
    low.assign(n, 0);
    isCut.assign(n, false);
    bridges.clear();
    timer = 0;
    for (int i = 0; i < n; ++i)
      if (dfn[i] == 0) dfs(i, -1, adj);
  }
};

注意这里用「父边编号」而非父节点来跳过回头–这正确处理了重边的情况（两条平行边不会被误判为环或忽略）。

下面用一张 7 节点无向图展示 dfn、low 与割点/桥判定：

Tarjan 示例 (无向图, 标注 (dfn,low)):

       1(1,1)         回边: 4 -> 2
      / \            (4 连回祖先 2)
     2(2,2)  5(5,5)
     |        |
     3(3,2)  6(6,6)   回边把 low[4]
     |        |       拉到 dfn[2]=2,
     4(4,2)  7(7,7)   进而 low[3]=low[2]=2

割点: 1(根,2子) 2(low[3]>=dfn[2])
      5(low[6]>=dfn[5]) 6(low[7]>=dfn[6])
桥: 1-2, 1-5, 5-6, 6-7
非桥: 2-3, 3-4 (回边 4->2 使子树可达 2)

这个例子很好地展示了割点与桥的差异：节点 2 是割点，但边 2-3 不是桥–因为回边 4->2 让 3 的子树能绕过边 2-3 到达节点 2。

有向图强连通分量（SCC）

强连通分量（SCC）是有向图中任意两点互相可达的最大节点集。Tarjan 的 SCC 算法维护一个栈，保存「尚未归入任何 SCC 的灰节点」。当 dfn[u] == low[u] 时，说明 $u$ 是某个 SCC 的根，弹栈直到 $u$（含 $u$），弹出的节点构成一个 SCC。

#include <vector>
#include <stack>

struct TarjanSCC {
  int timer = 0;
  std::vector<int> dfn, low, sccId;
  std::vector<bool> inStack;
  std::stack<int> stk;
  int sccCount = 0;

  void dfs(int u,
      const std::vector<std::vector<int>>& adj) {
    dfn[u] = low[u] = ++timer;
    stk.push(u);
    inStack[u] = true;
    for (int v : adj[u]) {
      if (dfn[v] == 0) {          // 树边
        dfs(v, adj);
        low[u] = std::min(low[u], low[v]);
      } else if (inStack[v]) {    // 回边 (v 在栈中)
        low[u] = std::min(low[u], dfn[v]);
      }
      // 横叉边/前向边: inStack[v]=false, 不更新
    }
    if (dfn[u] == low[u]) {       // u 是 SCC 根
      while (true) {
        int v = stk.top();
        stk.pop();
        inStack[v] = false;
        sccId[v] = sccCount;
        if (v == u) break;
      }
      ++sccCount;
    }
  }

  void run(int n,
      const std::vector<std::vector<int>>& adj) {
    dfn.assign(n, 0);
    low.assign(n, 0);
    inStack.assign(n, false);
    sccId.assign(n, -1);
    sccCount = 0;
    for (int i = 0; i < n; ++i)
      if (dfn[i] == 0) dfs(i, adj);
  }
};

dfn[u] == low[u] 的含义：$u$ 无法通过回边到达比自己更早的祖先，因此 $u$ 是其所在 SCC 中「最早发现」的节点（SCC 的根）。栈中 $u$ 上方的节点都是 $u$ 的子树中尚未归入其他 SCC 的节点，它们与 $u$ 互相可达，构成一个 SCC。

关键区别：SCC 的回边更新条件是 inStack[v]（$v$ 在栈中），而非简单的「已访问」。因为只有栈中节点才可能是当前 SCC 的成员；已弹出（归入其他 SCC）的节点是横叉边的终点，不应更新 low。这是 SCC 与无向图 Tarjan 的核心差异。

应用：2-SAT。2-SAT 问题中每个约束形如「$a$ 或 $b$」，可建模为有向图（变量及其否定互为后继）。缩点后按拓扑逆序赋值：若 $x$ 与 $\neg x$ 在同一 SCC 则无解；否则按 SCC 拓扑序，排在后面的 SCC 先赋值为真。Tarjan SCC 天然按逆拓扑序产出 SCC 编号（先弹出的 SCC 在拓扑序中靠后），无需额外排序。

与并查集的分工。并查集做动态连通性（不断合并 + 查询），Tarjan 做一次性静态分析（割点/桥/SCC）。并查集处理无向图的连通分量，无法求割点/桥；Tarjan 能求割点/桥/SCC 但不支持动态加边。两者互补，详见 并查集。

复杂度 $O(V + E)$，一次 DFS 完成–这是 Tarjan 算法的精妙之处。

网格 DFS：岛屿与 Flood Fill

网格是「伪装成矩阵的图」：每格一节点，四邻接为边。岛屿问题与 flood fill 是网格 DFS 的核心应用。网格最短步数问题则归 BFS，详见 BFS 专篇；本节只讲连通性、flood fill 与枚举。

岛屿数量（LeetCode 200）

遍历每个格子，遇 '1'（陆地）且未访问则 DFS 标记整个连通块，计数加一。

#include <vector>

class Solution {
  int m, n;
  const int dx[4] = {0, 0, 1, -1};
  const int dy[4] = {1, -1, 0, 0};

  void dfs(std::vector<std::vector<char>>& grid,
           int x, int y) {
    if (x < 0 || x >= m || y < 0 || y >= n) return;
    if (grid[x][y] != '1') return;  // 水或已访问

    grid[x][y] = '2';               // 原地标记, 省 visited
    for (int i = 0; i < 4; ++i) {
      dfs(grid, x + dx[i], y + dy[i]);
    }
  }
public:
  int numIslands(std::vector<std::vector<char>>& grid) {
    m = grid.size();
    n = grid[0].size();
    int cnt = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == '1') {
          dfs(grid, i, j);
          ++cnt;                    // 每启动一次多一座岛
        }
      }
    }
    return cnt;
  }
};

思路解读。外层双重循环枚举每个格子作为 DFS 起点，与图的连通分量计数完全同构。dfs 用原地修改（'1' -> '2'）省去 visited 数组，是网格题的常用技巧。边界检查写在递归入口处：先判越界，再判格子内容，避免下标越界。

复杂度。$O(m \times n)$，每格至多访问一次。

岛屿最大面积（LeetCode 695）

DFS 返回当前连通块大小（1 + 四方向递归之和），取所有起点的最大值。这演示了 DFS 返回值自底向上聚合的范式–后序在「离开节点时」把子树信息合并到父。

#include <vector>
#include <algorithm>

class Solution {
  int m, n;
  const int dx[4] = {0, 0, 1, -1};
  const int dy[4] = {1, -1, 0, 0};

  int dfs(std::vector<std::vector<int>>& grid,
          int x, int y) {
    if (x < 0 || x >= m || y < 0 || y >= n) return 0;
    if (grid[x][y] != 1) return 0;

    grid[x][y] = 0;                 // 标记已访问
    int area = 1;                   // 当前格子贡献 1
    for (int i = 0; i < 4; ++i) {
      area += dfs(grid, x + dx[i], y + dy[i]);
    }
    return area;                    // 后序: 子树面积之和
  }
public:
  int maxAreaOfIsland(
      std::vector<std::vector<int>>& grid) {
    m = grid.size();
    n = grid[0].size();
    int best = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1) {
          best = std::max(best, dfs(grid, i, j));
        }
      }
    }
    return best;
  }
};

area = 1 + Σ dfs(邻居) 是后序聚合的典型写法：先把当前格子标记并贡献 1，再递归四个方向收集子连通块的面积，返回总和。这与表达式树求值 l + r 的结构同构。岛屿周长问题同理：DFS 中统计边界贡献（相邻为水或越界则贡献 1）。

被围绕的区域（LeetCode 130）

从四条边的 'O' 出发 DFS 标记「不被围绕」的 O，剩余的 O 翻转为 X。这是边界 flood fill 范式。

#include <vector>

class Solution {
  int m, n;
  const int dx[4] = {0, 0, 1, -1};
  const int dy[4] = {1, -1, 0, 0};

  void dfs(std::vector<std::vector<char>>& board,
           int x, int y) {
    if (x < 0 || x >= m || y < 0 || y >= n) return;
    if (board[x][y] != 'O') return;

    board[x][y] = '#';              // 标记"不被围绕"
    for (int i = 0; i < 4; ++i) {
      dfs(board, x + dx[i], y + dy[i]);
    }
  }
public:
  void solve(std::vector<std::vector<char>>& board) {
    m = board.size();
    if (m == 0) return;
    n = board[0].size();
    // 从四条边的 O 出发 flood fill
    for (int i = 0; i < m; ++i) {
      dfs(board, i, 0);
      dfs(board, i, n - 1);
    }
    for (int j = 0; j < n; ++j) {
      dfs(board, 0, j);
      dfs(board, m - 1, j);
    }
    // '#' 不被围绕恢复为 O, 剩余 O 翻转为 X
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (board[i][j] == 'O') board[i][j] = 'X';
        else if (board[i][j] == '#') board[i][j] = 'O';
      }
    }
  }
};

思路解读。被围绕的 O 无法到达边界，因此从边界 O 出发 flood fill 标记的 O 一定不被围绕。标记完后，未被标记的 O 就是被围绕的，翻转为 X。这种「从边界反向标记」的思路在太平洋大西洋水流等问题中也常见。

Flood Fill 总结

Flood fill（种子填充）是画图软件「油漆桶」的原理：从一点出发 DFS 把连通同色区域改成新色。原地修改技巧（'1' -> '2'、'O' -> '#'）省去额外 visited，是网格 DFS 的标配。注意求所有解时 DFS 后需恢复原值，求连通块标记或一解时则无需恢复。

网格 DFS：单词搜索

单词搜索（LeetCode 79）是「网格 DFS + 回溯」的典型：从每个起点出发，沿四方向匹配 word 的下一字符，同一格子不能重复使用。

#include <vector>
#include <string>

class Solution {
  int m, n;
  const int dx[4] = {0, 0, 1, -1};
  const int dy[4] = {1, -1, 0, 0};

  bool dfs(std::vector<std::vector<char>>& board,
           const std::string& word,
           int x, int y, int k) {
    if (k == (int)word.size()) return true;
    if (x < 0 || x >= m || y < 0 || y >= n) return false;
    if (board[x][y] != word[k]) return false;

    char tmp = board[x][y];
    board[x][y] = '#';              // 做选择: 标记已访问
    for (int i = 0; i < 4; ++i) {
      if (dfs(board, word,
              x + dx[i], y + dy[i], k + 1))
        return true;                // 找到一个解即返回
    }
    board[x][y] = tmp;              // 撤销选择: 恢复
    return false;
  }
public:
  bool exist(std::vector<std::vector<char>>& board,
             std::string word) {
    m = board.size();
    n = board[0].size();
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (dfs(board, word, i, j, 0))
          return true;
      }
    }
    return false;
  }
};

从 DFS 视角看。外层枚举每个格子作为匹配起点，dfs(x, y, k) 表示从 (x, y) 出发匹配 word[k..]。原地标记（board[x][y] = '#'）避免重复使用同一格子，回溯时恢复原字符–这就是「做选择/撤销选择」。

复杂度。$O(m \cdot n \cdot 3^L)$，其中 $L$ 是单词长度。首步有 4 方向，后续每步至多 3 方向（不回头到刚来的格子，因已标记）。

优化。反向单词：统计首尾字符频率，若 word[0] 在网格出现次数多于 word.back()，则反转 word 再搜，分支因子显著降低。多词搜索（单词搜索 II）用 Trie 同步下降，网格只扫一遍。

单词搜索是回溯的样板题，「做选择/撤销选择」的逐行讲解与回溯模板的完整分析见 回溯算法 单词搜索节，本文只给 DFS 骨架与原地标记技巧，不重复其回溯细节。

DFS 与回溯的关系

回溯是 DFS 在「决策树」上的应用。两者共享同一套「深入-回退」的递归栈机制，差别在标记语义。

图 DFS (永久 visited)        决策树回溯 (临时标记 + 撤销)

  1──2──3                       [] (根)
       │                       /  |  \
       4                      [1] [2] [3]
                                 / \
  访问 2 后永久标记,           [1,2][1,3]
  visited[2]=true 永不撤销     path=[1,2] -> 收集 -> pop -> 撤销

标记语义:
  图: "此点已收入解集"          决策树: "此选择在当前路径已用"
  全局一次, 不可逆              路径回退后撤销, 可重选

统一视角。图 DFS 遍历「图的节点」，回溯遍历「决策树的节点」，底层都是「深入-回退」。但图 DFS 的 visited 是永久标记（每点访问一次，因为图的连通性是确定的）；回溯的标记是临时标记（路径回退后撤销，因为决策树中同一选择层可重复进入–比如全排列里数字 1 可以出现在不同位置）。

何时叫 DFS、何时叫回溯。遍历确定结构（图/树/网格连通性、flood fill）叫 DFS；在指数级状态空间枚举方案（排列、组合、子集、N 皇后、数独）叫回溯。分界线是「状态空间是否是指数级的隐式决策树」。

排列、组合、子集、N 皇后、数独、分割回文串的完整模板与剪枝详解均在 回溯算法，本文不重复。两者共有的陷阱是栈溢出与递归深度；回溯特有的陷阱是「撤销遗漏」–做了选择却忘了在递归返回后撤销。

剪枝

剪枝是「在展开子树前判断其无望并跳过」，是 DFS/回溯从指数爆炸走向可用的关键。

可行性剪枝

当前路径已违反约束，子树无解，立即剪。网格 DFS 中的越界检查、单词搜索的字符不匹配、数独的冲突检测都属此类。这是最基础也最有效的剪枝。

最优性剪枝（界限）

求最优解时，当前累计代价已劣于已知最优则剪。常配合「乐观下界估计」：当前代价 + 剩余最小可能代价 $\ge$ 最优，则剪。

以数字组合之和为例（求凑成目标和的最少数字数）：

#include <vector>
#include <algorithm>

void dfs(const std::vector<int>& cand, int start,
         int remain, int cnt, int& best) {
  if (remain == 0) {
    best = std::min(best, cnt);
    return;
  }
  // 最优性剪枝: 已用数字数 >= best, 不可能更优
  if (cnt >= best) return;
  for (int i = start; i < (int)cand.size(); ++i) {
    if (cand[i] > remain) break;  // 可行性剪枝
    dfs(cand, i, remain - cand[i],
        cnt + 1, best);
  }
}

if (cnt >= best) return 是最优性剪枝：当前已用数字数不小于已知最优，继续搜不可能改进。if (cand[i] > remain) break 是可行性剪枝（排序保证后续更大）。

记忆化剪枝

若状态 (u, 状态) 已被更优地访问过，则剪–这正是 DP 的雏形。当重叠子问题足够多、状态可哈希时，记忆化剪枝演化为记忆化搜索，即自顶向下的 DP。记忆化与递推的取舍见 动态规划 记忆化与递推取舍节。

启发式排序

不改变正确性，但改变分支展开顺序：先展开「更有希望」的分支，让剪枝更早生效。常见策略是 MRV（Minimum Remaining Values）–选候选最少的位置先试。数独的「候选最少格优先」即此。

剪枝不改变最坏复杂度（最坏情况下还是没得剪），但常把实际规模压几个数量级。一个通用原则：剪枝越早越好，在更靠近根的位置剪掉一棵子树，省下的是整棵子树的代价。N 皇后、数独的剪枝细节见 回溯算法 剪枝艺术节。

迭代加深 IDDFS 与 IDA*

DFS 省内存但可能在无解分支上无限深探；BFS 完备且找最短但内存 $O(b^d)$ 爆炸。迭代加深 DFS（IDDFS）取两者之长：用「限制深度逐步加深」的多次 DFS，取得 BFS 的完备性与 DFS 的省内存。

IDDFS

#include <vector>

bool dfs(const std::vector<std::vector<int>>& adj,
         int u, int target, int depth, int limit,
         std::vector<bool>& vis) {
  if (depth > limit) return false;
  if (u == target) return true;    // 找到目标
  vis[u] = true;
  for (int v : adj[u]) {
    if (!vis[v]) {
      if (dfs(adj, v, target, depth + 1, limit, vis))
        return true;
    }
  }
  vis[u] = false;                  // 回溯: 供同层其他路径用
  return false;
}

bool iddfs(int start, int target,
           const std::vector<std::vector<int>>& adj) {
  int n = adj.size();
  for (int limit = 0; limit <= n; ++limit) {
    std::vector<bool> vis(n, false);
    if (dfs(adj, start, target, 0, limit, vis))
      return true;                 // 在深度 limit 内找到
  }
  return false;
}

每次 dfs 限制最大深度为 limit，从 0 逐步加深到 $n$。重复展开上层的代价可忽略：深度 $d$ 的搜索代价是 $b^d$（$b$ 为分支因子），总代价 $1 + b + b^2 + \dots + b^d = O(b^d)$，与 BFS 同阶。而空间只需 $O(d)$（递归栈深度），与 DFS 相同。这是 IDDFS 最精妙的取舍：用「时间常数翻倍」换「空间从 $O(b^d)$ 降到 $O(d)$」。

注意 IDDFS 的 visited 是临时标记（回溯时撤销），与普通图 DFS 的永久标记不同–因为同一节点可能在不同的深度受限路径中被重复访问。

IDA*

IDA* 是 IDDFS 的启发式增强：用估价函数 $f = g + h$ 代替纯深度限制。阈值从 $h(\text{start})$ 起，每轮取上一轮所有超阈节点中的最小 $f$ 值作新阈值。

#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>

// 启发式: 曼哈顿距离 (四方向移动可采纳)
inline int heuristic(int x, int y, int tx, int ty) {
  return std::abs(x - tx) + std::abs(y - ty);
}

// dfs 前向声明 (定义在 idaStar 之后)
bool dfs(int x, int y, int g, int tx, int ty,
         const std::vector<std::vector<int>>& grid,
         int threshold, int& nextThr);

// IDA* 骨架 (以网格最短路为例)
int idaStar(int sx, int sy, int tx, int ty,
            const std::vector<std::vector<int>>& grid) {
  int h0 = heuristic(sx, sy, tx, ty);
  int threshold = h0;
  while (true) {
    int nextThreshold = INT_MAX;
    if (dfs(sx, sy, 0, tx, ty, grid,
            threshold, nextThreshold))
      return threshold;            // 找到, 返回代价
    if (nextThreshold == INT_MAX)
      return -1;                   // 无解
    threshold = nextThreshold;     // 加深阈值
  }
}

// g = 已走代价, f = g + h
bool dfs(int x, int y, int g, int tx, int ty,
         const std::vector<std::vector<int>>& grid,
         int threshold, int& nextThr) {
  int h = heuristic(x, y, tx, ty);
  int f = g + h;
  if (f > threshold) {
    nextThr = std::min(nextThr, f);
    return false;                  // 超阈, 记录最小超阈值
  }
  if (x == tx && y == ty) return true;
  // 枚举四方向递归 (略)
  // for each neighbor (nx, ny):
  //   if dfs(nx, ny, g+1, ...) return true;
  return false;
}

heuristic 是到终点的估计代价（如曼哈顿距离）。$h=0$ 时 IDA* 退化为 IDDFS；$h$ 恰为真实距离时 IDA* 沿最优路径直奔终点。可采纳性（admissible）要求 $h$ 永不高估真实最短距离，这是 IDA* 给出最优解的充要条件。

适用场景。解深度大但未知、状态空间庞大（15 数码、魔方、埃及分数）、A* 的优先队列内存吃紧时。IDA* 是 A* 的「深度受限迭代加深版」，用阈值代替开放集。骑士周游（Knight Tour）也可用 IDDFS/IDA* 求解：在 $8 \times 8$ 棋盘上找一条经过所有格子的马步路径，解深度为 64 但分支因子不固定，Warnsdorff 启发式（优先走出口最少的格子）配合 IDDFS 是经典解法。

与双向 BFS 的对称性：双向 BFS 是空间换时间，IDA* 是时间换空间，两者都是「单向搜索不够用」时的优化，可对照 BFS 专篇 阅读。

横向对比 DFS vs BFS

一句话对照：DFS 用栈深探优先（省内存、适合找任意解/枚举/拓扑/Tarjan），BFS 用队列逐层扩展（找无权最短路/最小步数）。

• 选 DFS：连通性判断、拓扑排序、割点/桥/SCC、回溯枚举、深解空间。
• 选 BFS：无权最短路、最小步数、层序信息。

详细的对比表（数据结构、完备性、最短路径、内存、典型场景）见 BFS 专篇，本文不重复。两者共享 visited 机制与方向数组模板，差别只在容器（栈 vs 队列）与推进顺序。

实战场景：竞赛与工程

竞赛

DFS 是算法竞赛搜索与图论的基石：

• 图论：连通块计数、拓扑排序、Tarjan 割点/桥/SCC 是 Div.2 C/D 的常客。Tarjan 的 low 更新细节（回边用 dfn[v] 而非 low[v]、横叉边不更新）是高频考点。
• 搜索：回溯 + 剪枝 + IDDFS 是搜索题的三大武器。网格图 DFS 常数小但注意栈溢出（链状网格 $n = 10^5$ 时可手动开栈或改迭代）。
• 树形 DP 与树链剖分：底层遍历是 DFS 后序，详见 动态规划 树形 DP 节。
• 网格搜索：岛屿、flood fill、单词搜索是面试高频。

工程

DFS 在工程中是依赖分析、连通性求解、编译器遍历、垃圾回收的底层工具：

• 依赖解析：make/cargo/webpack 的依赖图拓扑排序、循环依赖检测。cargo 检测 crate 循环依赖本质上就是有向图三色标记。
• 连通性：网络分区分析、集群可达性判断。
• 编译器：AST 遍历（语法分析）、控制流图（CFG）可达性分析（死代码消除的本质是 DFS 标记可达基本块）。
• 求解器：SAT/约束求解器内部的 CDCL（Conflict-Driven Clause Learning）本质是带学习的 DFS。
• 运行时：文件系统递归遍历、git commit DAG 遍历、GC 标记-清除的「标记」阶段即图 DFS（从根集出发标记所有可达对象）。

工程教训。生产代码要警惕递归栈溢出（深链/深树场景），改迭代或显式栈；警惕指数爆炸，给搜索加深度/时间上限。一个真实案例：用户构造恶意正则触发灾难性回溯，本质是 DFS 在无剪枝的隐式树上指数级展开。

常见陷阱与边界条件

DFS 代码看似简单，但以下高频踩坑点值得逐条排查：

1. 访问标记时机。必须「首次进入节点时」立即标记，而非「处理完邻居后」。后者会让同一节点在栈中重复出现，时空退化。正确：dfs(u) 第一行就 vis[u] = true。

2. 迭代 DFS 重复入栈。弹栈才标记会让节点多次入栈（多个前驱各压一次）。入栈即标记可避免，但需注意压栈顺序要逆序以复现递归的访问顺序。

3. 方向数组写错。dx/dy 配对错位致方向错乱。常用 {0,0,1,-1} / {1,-1,0,0}（右左下上）。自检手段：打印移动后的坐标验证。

4. 无向图环检测父节点陷阱。传 parent 判 v != parent，但重边会误判（两点间两条平行边，v 是父节点但非同一条边）。正确做法传「父边编号」而非父节点，见上方 Tarjan 代码。

5. 三色标记忘涂黑。递归返回前必须 color[u] = 2，否则后续从其他路径到达该节点时误判为环（灰色 = 栈中祖先，但此时它已不在栈中）。

6. 栈溢出。递归深度 = 图最长链，链状图 $n = 10^5 \sim 10^6$ 爆栈。对策：竞赛用 #pragma comment(linker, "/STACK:...") 或 ulimit -s 开大栈；改迭代；或用 IDDFS 限制深度。

7. 网格 DFS 越界顺序。必须先判越界再访问 board[x][y]，否则下标越界段错误。正确：if (x<0 || x>=m || y<0 || y>=n) return; 在最前面。

8. 原地修改未恢复。求所有解时必须恢复 board[x][y]，否则污染后续搜索。求一解（找到即返回）可不恢复–反正不再用。这是「求一解」与「求全解」在代码上的微妙差异。

9. Tarjan low 更新错误。回边用 dfn[v] 更新（不是 low[v]）；横叉边/前向边不更新（SCC 中 inStack[v]=false 的边）。低级但致命，是 Tarjan 最常见的 bug。

10. 拓扑排序逆后序写反。直接用后序（push_back 顺序）而非逆后序（reverse 后），依赖关系颠倒。记住：最晚涂黑的节点（被依赖最多）应在拓扑序最前。

11. 起点 visited 漏标。主循环调用 dfs(i) 前，dfs 内部第一行就标记 vis[i]。若在 dfs 外部标记又不在内部标记，或反过来重复标记，逻辑会乱。统一在 dfs 入口标记。

12. 多连通图主循环遗漏。必须 for i in 0..n: if !vis[i] then dfs(i)，否则漏掉非起点连通块。这是连通分量计数、拓扑排序、环检测的共同前提。

小结

DFS 的三句话本质：

1. 沿一条路深探到底、无路则回退到最近有未访问邻居的祖先。递归调用栈天然提供回退机制，迭代栈与之等价。
2. visited / 三色标记保证每点访问一次，并支撑环检测、拓扑排序、Tarjan 等高阶应用。
3. 模板的四个可插拔点（前序动作、后序动作、剪枝条件、答案收集）覆盖了从连通分量到 Tarjan 的所有应用。

学习路线：通用模板 -> 树的前中后序 -> 图连通分量/环检测/拓扑 -> 网格岛屿 -> Tarjan -> 剪枝 -> IDDFS/IDA*。每一步都是在模板的某个插点填入特定内容。

与同系列的关系：回溯是 DFS 在决策树上的特化（见 回溯算法），BFS 是 DFS 的「逐层版」对照（见 BFS 专篇），记忆化 DFS 是自顶向下的 DP（见 动态规划），并查集是动态连通性的替代方案（见 并查集）。

DFS 的精神：不追求「更优复杂度」（最坏仍是 $O(V+E)$ 遍历或指数搜索），而追求「用最少的机制（一个栈 + 一个 visited）覆盖最多的搜索场景」。从迷宫找路到 Tarjan 求割点，从岛屿计数到 SAT 求解器的 CDCL，底层都是同一套「深入-回退」的骨架。理解了这套骨架，再面对陌生问题时，只需问一句「四个插点该填什么」，就能把 DFS 从模板变成工具。