先搜索递归与深度优先搜索的关系递归与系统栈递归调用的过程栈的作用

DFS

DFS是图论和树结构中常用的遍历算法之一。

在解决许多递归问题、图的连通性问题、路径搜索、迷宫问题等场景时DFS

先探索一个节点的所有后代直到无法继续深入为止然后再回溯到上一个节点。

DFS

可以通过递归或使用栈的方式实现常用于遍历图、树等数据结构。

理解和掌握

DFS

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

想象你在一个迷宫里探险DFS

从入口出发你会选择一条通道并一直走下去尽量往迷宫的最深处走直到遇到死路或走到终点。

如果遇到了死路你会回头走到最近的分叉点再选择另一条没走过的路继续深入。

重复这个过程直到你探索完所有的路。

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

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

选一个起点从根节点或任意节点开始。

深入搜索沿着一条路径走下去直到叶子节点或遇到死路。

回溯如果某条路走不通回到上一个分叉点换另一条路继续。

继续探索直到所有节点都被访问过。

DFS

通常用递归的方式来实现因为递归天然适合这种“深入再回头”的过程。

栈结构如果不用递归DFS

也可以通过一个栈stack来实现因为栈的后进先出LIFO机制可以很好地支持这种“深入再回溯”的过程。

找到的路径可能不是最短的DFS

走得很深但不一定是最短路径因为它不保证先找到的路径就是最优解。

深度优先搜索的方法是你进入楼后走进第一间房间再走到房间里的每个子房间如果有的话一直探索到底。

当你走到尽头后再回到上一个房间换下一条路继续探索。

这种方法总是优先深入到最里面而不是先检查所有房间。

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

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

递归递归是一种解决问题的方式通过让函数调用自身来逐步解决子问题。

当我们用递归解决一个问题时先把问题逐步分解成更小的子问题然后等每个子问题解决后依次返回结果。

深度优先搜索DFS

会沿着一个分支一直深入到最深处然后再回溯到上一个节点继续探索其他分支。

因此当用递归实现

时递归的过程就是深度优先地一层一层深入到子问题或子节点直到不能再深入为止。

这就是为什么递归天然适合实现深度优先搜索。

递归与系统栈

递归函数在执行时每次调用函数自身时都会将当前的函数状态变量、指针等压入系统栈这就像给函数按下了一个“暂停键”保存了当前状态。

等递归深入到最底层时递归开始“回溯”即逐层从栈中取出保存的状态恢复之前暂停的函数执行直到所有递归调用都结束。

递归进入每次调用自身时都会将当前函数状态比如局部变量、参数等压入栈中递归继续深入。

这个过程不断往下直到达到基准条件或不能再递归时停止。

递归回溯当递归到达最深处时会回到上一个调用点将之前的状态从栈中取出恢复函数执行直到完成整个递归。

DFS

栈stack是一种后进先出LIFO的数据结构。

递归调用时系统使用栈来保存每一层函数调用的状态这样可以在函数返回时恢复之前的状态。

系统栈负责管理递归函数的调用关系。

在

DFS

中递归函数每深入到下一层当前的计算状态就会被压入栈等到回溯时再从栈中弹出并继续执行。

递归实现

}这个递归函数在每次进入时会将当前节点的状态压入栈进入左子树或右子树的递归调用。

当到达叶子节点无子节点时函数返回并从栈中恢复上一个状态继续未完成的任务。

这个过程就是

深度优先搜索

时当前函数状态被压入栈等函数返回时从栈中弹出并恢复执行。

栈的状态会在递归过程中像“弹簧”一样收缩和扩展逐层管理函数调用。

好的下面我将用字符串图一步一步展示深度优先搜索DFS时系统栈的变化。

假设我们有一棵二叉树结构如下

E步骤

深度优先搜索会在每次访问新节点时将其压入系统栈直到无法继续深入遇到叶子节点。

遇到叶子节点或无子节点时递归回溯栈中的节点逐步弹出。

这个过程就是栈的“深入push-回溯pop”操作的完整体现。

DFS

深度优先搜索是一种通过递归或显式栈来实现的遍历算法具有简单且直观的特点。

在遍历图或树结构时它优先深入探索某一路径遇到叶子节点或无法继续时再回溯。

DFS

在路径搜索、连通性判定、强连通分量分析等问题中有广泛的应用。

掌握

DFS

有助于理解更多高级算法的实现并为解决复杂问题提供了一种基本的思路。