Python算法：深度优先搜索—DFS（模板及其样例）_python dfs

深度优先搜索搜索

• 沿着一条路径一直搜索下去，在无法搜索时，回退到刚刚访问过的节点。

• 并且每个节点只能访问一次。

• 本质上是持续搜索，遍历了所有可能的情况，必然能得到解。

• 流程是一个树的形式，每次一条路走到黑。

• 目的主要是达到被搜索结构的叶结点直到最后一层，然后回退到上层，被 访问过的节点会被标记，然后查看是否有其他节点，如果有则继续下一层 ，直到最后一层。一次类推直到所有节点都被查找。

【思想】

后访问的节点，其邻接点先被访问。

根据深度优先遍历的定义，后来的先搜索（栈、递归）。

【步骤】

①初始化图中的所有节点为均未被访问。

②从图中的某个节点v出发，访问v并标记其已被访问。

③依次检查v的所有邻接点w，如果w未被访问，则从w出发进行

深度优先遍历（递归调用，重复步骤（2）和（3））。

 样例：一只老鼠走迷宫 

DFS访问示例

DFS的常见操作 

 DFS基础：递归和记忆化搜索

 斐波那契数列

 

 

 

改进：记忆化 

 DFS的代码框架

 DFS样例：搜索和输出所有路径

   

提示：