CSP-J 算法基础 深度优先搜索

前言

深度优先搜索（Depth First Search, DFS）是图论和树结构中常用的遍历算法之一。在解决许多递归问题、图的连通性问题、路径搜索、迷宫问题等场景时，DFS 都扮演了重要角色。通过“深入”的方式，DFS 先探索一个节点的所有后代，直到无法继续深入为止，然后再回溯到上一个节点。DFS 可以通过递归或使用栈的方式实现，常用于遍历图、树等数据结构。理解和掌握 DFS 是许多复杂算法的基础，特别是在图论中的应用。

深度优先搜索

深度优先搜索（DFS，Depth-First Search）是一种在遍历或搜索树和图结构时常用的算法，简单来说，它的工作方式是：沿着一条路径尽可能深地走下去，直到不能再深入为止，然后回头去找其他还没走过的路径。

通俗解释

想象你在一个迷宫里探险，DFS 的方式就像这样：

1. 从入口出发，你会选择一条通道，并一直走下去，尽量往迷宫的最深处走，直到遇到死路或走到终点。
2. 如果遇到了死路，你会回头走到最近的分叉点，再选择另一条没走过的路继续深入。
3. 重复这个过程，直到你探索完所有的路。

这就像你先走得尽量深，而不是先广泛地探索所有的通道，这就是“深度优先”的意思。

例子

如果你要在一棵树里找到某个特定的节点，深度优先搜索会从根节点开始，一直沿着某条分支走到底，如果这条路径没有找到目标节点，就回到上一个节点，换另一条路径继续搜索。

深度优先搜索的步骤

1. 选一个起点：从根节点（或任意节点）开始。
2. 深入搜索：沿着一条路径走下去，直到叶子节点或遇到死路。
3. 回溯：如果某条路走不通，回到上一个分叉点，换另一条路继续。
4. 继续探索：直到所有节点都被访问过。

DFS 的特点

• 递归：DFS 通常用递归的方式来实现，因为递归天然适合这种“深入再回头”的过程。
• 栈结构：如果不用递归，DFS 也可以通过一个栈（stack）来实现，因为栈的后进先出（LIFO）机制可以很好地支持这种“深入再回溯”的过程。
• 找到的路径可能不是最短的：DFS 走得很深，但不一定是最短路径，因为它不保证先找到的路径就是最优解。

生活中的类比

想象你要检查一个楼里的每一层房间：

• 深度优先搜索的方法是：你进入楼后，走进第一间房间，再走到房间里的每个子房间（如果有的话），一直探索到底。当你走到尽头后再回到上一个房间，换下一条路继续探索。
• 这种方法总是优先深入到最里面，而不是先检查所有房间。

这就是深度优先搜索，一个专注于尽量深入探索的搜索策略。

为什么递归问题会变成深度优先搜索？

递归和深度优先搜索（DFS）之间有天然的联系，因为递归本质上是“先深入再回溯”的过程，而这正是深度优先搜索的核心思想。

递归与深度优先搜索的关系：

• 递归：递归是一种解决问题的方式，通过让函数调用自身来逐步解决子问题。当我们用递归解决一个问题时，先把问题逐步分解成更小的子问题，然后等每个子问题解决后，依次返回结果。
• 深度优先搜索：DFS 也是一步步深入探索的过程。在树或图的结构中，DFS 会沿着一个分支一直深入到最深处，然后再回溯到上一个节点，继续探索其他分支。

因此，当用递归实现 DFS 时，递归的过程就是深度优先地一层一层深入到子问题（或子节点），直到不能再深入为止。这就是为什么递归天然适合实现深度优先搜索。

递归与系统栈

递归函数在执行时，每次调用函数自身时，都会将当前的函数状态（变量、指针等）压入系统栈，这就像给函数按下了一个“暂停键”，保存了当前状态。等递归深入到最底层时，递归开始“回溯”，即逐层从栈中取出保存的状态，恢复之前暂停的函数执行，直到所有递归调用都结束。

递归调用的过程：

1. 递归进入：每次调用自身时，都会将当前函数状态（比如局部变量、参数等）压入栈中，递归继续深入。这个过程不断往下，直到达到基准条件或不能再递归时停止。
2. 递归回溯：当递归到达最深处时，会回到上一个调用点，将之前的状态从栈中取出，恢复函数执行，直到完成整个递归。

这与 DFS 的“深入再回溯”的过程完全一致。

栈的作用：

• 栈（stack）是一种后进先出（LIFO）的数据结构。递归调用时，系统使用栈来保存每一层函数调用的状态，这样可以在函数返回时恢复之前的状态。
• 系统栈负责管理递归函数的调用关系。在 DFS 中，递归函数每深入到下一层，当前的计算状态就会被压入栈，等到回溯时再从栈中弹出并继续执行。

递归与系统栈的简单示例

递归实现 DFS 的简单例子：

以树的前序遍历为例（先访问根节点，再访问左子树和右子树）：

void DFS(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 访问当前节点
    cout << root->val << " ";
    
    // 递归访问左子树
    DFS(root->left);
    
    // 递归访问右子树
    DFS(root->right);
}

这个递归函数在每次进入时，会将当前节点的状态压入栈，进入左子树或右子树的递归调用。当到达叶子节点（无子节点）时，函数返回，并从栈中恢复上一个状态，继续未完成的任务。这个过程就是 深度优先搜索 的实现。

递归和系统栈的可视化：

• 假设我们有一棵二叉树，DFS 从根节点 A 开始：

      A
     / \
    B   C
   / \
  D   E
  

• 递归过程：

  1. 调用 DFS(A)，进入 A 节点。
  2. 调用 DFS(B)，进入 B 节点。
  3. 调用 DFS(D)，进入 D 节点，到达叶子节点，递归开始回溯。
  4. 返回到 B，接着调用 DFS(E)。
  5. 返回到 A，然后调用 DFS(C)。

• 系统栈的变化：

  • 每次调用 DFS(X) 时，当前函数状态被压入栈，等函数返回时从栈中弹出并恢复执行。
  • 栈的状态会在递归过程中像“弹簧”一样收缩和扩展，逐层管理函数调用。

DFS时栈的变化

好的，下面我将用字符串图一步一步展示深度优先搜索（DFS）时系统栈的变化。假设我们有一棵二叉树，结构如下：

    A
   / \
  B   C
 / \
D   E

步骤 1：开始 DFS，从根节点 A 开始

• 访问 A
• 系统栈：[A]

Stack: A

步骤 2：访问左子树 B

• 进入节点 B
• 系统栈：[A, B]

Stack: A -> B

步骤 3：访问左子树 D

• 进入节点 D（D 是叶子节点，无子节点）
• 系统栈：[A, B, D]

Stack: A -> B -> D

步骤 4：D 没有子节点，回溯到 B

• 从 D 返回到 B
• 系统栈：[A, B]

Stack: A -> B

步骤 5：访问右子树 E

• 进入节点 E（E 也是叶子节点）
• 系统栈：[A, B, E]

Stack: A -> B -> E

步骤 6：E 没有子节点，回溯到 B，再回到 A

• 从 E 返回到 B，再回到 A
• 系统栈：[A]

Stack: A

步骤 7：访问右子树 `C

• 进入节点 C（C 是叶子节点）
• 系统栈：[A, C]

Stack: A -> C

步骤 8：C 没有子节点，回溯到 A

• 从 C 返回到 A
• 系统栈：[]（栈为空，DFS 完成）

Stack: (empty)

总结：

• 深度优先搜索会在每次访问新节点时将其压入系统栈，直到无法继续深入（遇到叶子节点）。
• 遇到叶子节点或无子节点时，递归回溯，栈中的节点逐步弹出。
• 这个过程就是栈的“深入（push）-回溯（pop）”操作的完整体现。

希望这个一步一步的字符串图能够帮助你理解 DFS 时栈的变化！

总结

深度优先搜索是一种通过递归或显式栈来实现的遍历算法，具有简单且直观的特点。在遍历图或树结构时，它优先深入探索某一路径，遇到叶子节点或无法继续时再回溯。DFS 在路径搜索、连通性判定、强连通分量分析等问题中有广泛的应用。掌握 DFS 有助于理解更多高级算法的实现，并为解决复杂问题提供了一种基本的思路。