您的位置:首页 > 娱乐 > 八卦 > CSP-J 算法基础 深度优先搜索

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

2024/12/23 6:36:38 来源:https://blog.csdn.net/m0_62599305/article/details/142259879  浏览:    关键词:CSP-J 算法基础 深度优先搜索

文章目录

  • 前言
  • 深度优先搜索
    • 通俗解释
    • 例子
    • 深度优先搜索的步骤
    • DFS 的特点
    • 生活中的类比
  • 为什么递归问题会变成深度优先搜索?
    • 递归与深度优先搜索的关系:
    • 递归与系统栈
      • 递归调用的过程:
      • 栈的作用:
    • 递归与系统栈的简单示例
      • 递归实现 DFS 的简单例子:
    • 递归和系统栈的可视化:
  • DFS时栈的变化
    • 步骤 1:开始 DFS,从根节点 `A` 开始
    • 步骤 2:访问左子树 `B`
    • 步骤 3:访问左子树 `D`
    • 步骤 4:`D` 没有子节点,回溯到 `B`
    • 步骤 5:访问右子树 `E`
    • 步骤 6:`E` 没有子节点,回溯到 `B`,再回到 `A`
    • 步骤 7:访问右子树 `C
    • 步骤 8:`C` 没有子节点,回溯到 `A`
      • 总结:
  • 总结


前言

深度优先搜索(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

  • 进入节点 DD 是叶子节点,无子节点)
  • 系统栈:[A, B, D]
Stack: A -> B -> D

步骤 4:D 没有子节点,回溯到 B

  • D 返回到 B
  • 系统栈:[A, B]
Stack: A -> B

步骤 5:访问右子树 E

  • 进入节点 EE 也是叶子节点)
  • 系统栈:[A, B, E]
Stack: A -> B -> E

步骤 6:E 没有子节点,回溯到 B,再回到 A

  • E 返回到 B,再回到 A
  • 系统栈:[A]
Stack: A

步骤 7:访问右子树 `C

  • 进入节点 CC 是叶子节点)
  • 系统栈:[A, C]
Stack: A -> C

步骤 8:C 没有子节点,回溯到 A

  • C 返回到 A
  • 系统栈:[](栈为空,DFS 完成)
Stack: (empty)

总结:

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

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


总结

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com