岳西县住房和城乡建设局网站,网站界面设计中的布局设计要注意什么的结合,科技小制作怎么做视频网站,html网页制作下载文章目录 前言深度优先搜索通俗解释例子深度优先搜索的步骤DFS 的特点生活中的类比 为什么递归问题会变成深度优先搜索#xff1f;递归与深度优先搜索的关系#xff1a;递归与系统栈递归调用的过程#xff1a;栈的作用#xff1a; 递归与系统栈的简单示例递归实现 DFS 的简… 文章目录 前言深度优先搜索通俗解释例子深度优先搜索的步骤DFS 的特点生活中的类比 为什么递归问题会变成深度优先搜索递归与深度优先搜索的关系递归与系统栈递归调用的过程栈的作用 递归与系统栈的简单示例递归实现 DFS 的简单例子 递归和系统栈的可视化 DFS时栈的变化步骤 1开始 DFS从根节点 A 开始步骤 2访问左子树 B步骤 3访问左子树 D步骤 4D 没有子节点回溯到 B步骤 5访问右子树 E步骤 6E 没有子节点回溯到 B再回到 A步骤 7访问右子树 C步骤 8C 没有子节点回溯到 A总结 总结 前言
深度优先搜索Depth First Search, DFS是图论和树结构中常用的遍历算法之一。在解决许多递归问题、图的连通性问题、路径搜索、迷宫问题等场景时DFS 都扮演了重要角色。通过“深入”的方式DFS 先探索一个节点的所有后代直到无法继续深入为止然后再回溯到上一个节点。DFS 可以通过递归或使用栈的方式实现常用于遍历图、树等数据结构。理解和掌握 DFS 是许多复杂算法的基础特别是在图论中的应用。 深度优先搜索
深度优先搜索DFSDepth-First Search是一种在遍历或搜索树和图结构时常用的算法简单来说它的工作方式是沿着一条路径尽可能深地走下去直到不能再深入为止然后回头去找其他还没走过的路径。
通俗解释
想象你在一个迷宫里探险DFS 的方式就像这样
从入口出发你会选择一条通道并一直走下去尽量往迷宫的最深处走直到遇到死路或走到终点。如果遇到了死路你会回头走到最近的分叉点再选择另一条没走过的路继续深入。重复这个过程直到你探索完所有的路。
这就像你先走得尽量深而不是先广泛地探索所有的通道这就是“深度优先”的意思。
例子
如果你要在一棵树里找到某个特定的节点深度优先搜索会从根节点开始一直沿着某条分支走到底如果这条路径没有找到目标节点就回到上一个节点换另一条路径继续搜索。
深度优先搜索的步骤
选一个起点从根节点或任意节点开始。深入搜索沿着一条路径走下去直到叶子节点或遇到死路。回溯如果某条路走不通回到上一个分叉点换另一条路继续。继续探索直到所有节点都被访问过。
DFS 的特点
递归DFS 通常用递归的方式来实现因为递归天然适合这种“深入再回头”的过程。栈结构如果不用递归DFS 也可以通过一个栈stack来实现因为栈的后进先出LIFO机制可以很好地支持这种“深入再回溯”的过程。找到的路径可能不是最短的DFS 走得很深但不一定是最短路径因为它不保证先找到的路径就是最优解。
生活中的类比
想象你要检查一个楼里的每一层房间
深度优先搜索的方法是你进入楼后走进第一间房间再走到房间里的每个子房间如果有的话一直探索到底。当你走到尽头后再回到上一个房间换下一条路继续探索。这种方法总是优先深入到最里面而不是先检查所有房间。
这就是深度优先搜索一个专注于尽量深入探索的搜索策略。
为什么递归问题会变成深度优先搜索
递归和深度优先搜索DFS之间有天然的联系因为递归本质上是“先深入再回溯”的过程而这正是深度优先搜索的核心思想。
递归与深度优先搜索的关系
递归递归是一种解决问题的方式通过让函数调用自身来逐步解决子问题。当我们用递归解决一个问题时先把问题逐步分解成更小的子问题然后等每个子问题解决后依次返回结果。深度优先搜索DFS 也是一步步深入探索的过程。在树或图的结构中DFS 会沿着一个分支一直深入到最深处然后再回溯到上一个节点继续探索其他分支。
因此当用递归实现 DFS 时递归的过程就是深度优先地一层一层深入到子问题或子节点直到不能再深入为止。这就是为什么递归天然适合实现深度优先搜索。
递归与系统栈
递归函数在执行时每次调用函数自身时都会将当前的函数状态变量、指针等压入系统栈这就像给函数按下了一个“暂停键”保存了当前状态。等递归深入到最底层时递归开始“回溯”即逐层从栈中取出保存的状态恢复之前暂停的函数执行直到所有递归调用都结束。
递归调用的过程
递归进入每次调用自身时都会将当前函数状态比如局部变量、参数等压入栈中递归继续深入。这个过程不断往下直到达到基准条件或不能再递归时停止。递归回溯当递归到达最深处时会回到上一个调用点将之前的状态从栈中取出恢复函数执行直到完成整个递归。
这与 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递归过程 调用 DFS(A)进入 A 节点。调用 DFS(B)进入 B 节点。调用 DFS(D)进入 D 节点到达叶子节点递归开始回溯。返回到 B接着调用 DFS(E)。返回到 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步骤 4D 没有子节点回溯到 B
从 D 返回到 B系统栈[A, B]
Stack: A - B步骤 5访问右子树 E
进入节点 EE 也是叶子节点系统栈[A, B, E]
Stack: A - B - E步骤 6E 没有子节点回溯到 B再回到 A
从 E 返回到 B再回到 A系统栈[A]
Stack: A步骤 7访问右子树 C
进入节点 CC 是叶子节点系统栈[A, C]
Stack: A - C步骤 8C 没有子节点回溯到 A
从 C 返回到 A系统栈[]栈为空DFS 完成
Stack: (empty)总结
深度优先搜索会在每次访问新节点时将其压入系统栈直到无法继续深入遇到叶子节点。遇到叶子节点或无子节点时递归回溯栈中的节点逐步弹出。这个过程就是栈的“深入push-回溯pop”操作的完整体现。
希望这个一步一步的字符串图能够帮助你理解 DFS 时栈的变化 总结
深度优先搜索是一种通过递归或显式栈来实现的遍历算法具有简单且直观的特点。在遍历图或树结构时它优先深入探索某一路径遇到叶子节点或无法继续时再回溯。DFS 在路径搜索、连通性判定、强连通分量分析等问题中有广泛的应用。掌握 DFS 有助于理解更多高级算法的实现并为解决复杂问题提供了一种基本的思路。
