前言
本篇文章首先来学习深度优先搜索算法（Depth-First-Search，DFS）
目录
1、本质
2、核心
3、框架
4、例题
正文
1、本质
深度优先搜索，又称为回溯法，其本质就是遍历整个搜索空间，找到给定问题的解
通俗来说就是暴力搜索，只是在这个过程中也有很多值得注意的地方
下面以树的深度优先搜索为例，先来直观上理解整个执行过程
顾名思义，深度优先的意思就是先选一条路走到底，走到无路可走就进行回溯（不撞南墙不回头）
具体遍历步骤如下：
| 当前节点 | 理想可选路径 | 实际可选路径 | 执行操作 | 实际选择路径 |
1 |
2 (未走)、3 (未走) |
2、3 |
深入 | 2 |
2 |
4 (未走)、5 (未走) |
4、5 |
深入 | 4 |
4 |
7 (未走)、8 (未走) |
7、8 |
深入 | |
7 |
/ |
/ |
回溯 | |
4 |
7 (已走)、8 (未走) |
8 |
深入 | |
8 |
/ |
/ |
回溯 | |
4 |
7 (已走)、8 (已走) |
/ |
回溯 | |
2 |
4 (已走)、5 (未走) |
5 |
深入 | |
5 |
9 (未走) |
9 |
深入 | |
9 |
/ |
/ |
回溯 | |
5 |
9 (已走) |
/ |
回溯 | |
2 |
4 (已走)、5 (已走) |
/ |
回溯 | |
1 |
2 (已走)、3 (未走) |
3 |
深入 | |
3 |
6 (未走) |
6 |
深入 | |
6 |
/ |
/ |
回溯 | |
3 |
6 (已走) |
/ |
回溯 | |
1 |
2 (已走)、3 (已走) |
/ |
结束 |
2、核心
深度优先搜索可以用递归实现，其中有几个核心概念：路径、选择列表、结束条件、约束条件
该怎么理解呢？假设我们现在站在某一个决策节点上（决策节点可以理解成上述树的节点）：
路径 ：表示在该节点之前曾经走过哪些节点（我从哪里来）
选择列表：表示在该节点之后可以走去哪些节点（我到哪里去）
结束条件：表示走到哪个节点停止
约束条件：表示哪个节点不能经过或没必要经过，也可以理解成剪枝条件
还是以上面的例子来说，假如我们现在站在节点 4，那么路径就是 1、2，选择列表就是 7、8
结束条件就是到达叶子节点，该题目隐含的约束条件就是已经走过的节点不能重复走
3、框架
深度优先搜索函数针对每个节点进行处理，输入某个节点的路径和选择列表，该函数完成以下的功能：
判断当前节点的路径是否满足结束条件
如果能够满足结束条件，当前路径即为合法路径，将其保存为答案
判断当前节点的路径是否满足约束条件
如果不能满足约束条件，当前路径即为非法路径，跳过后续的处理
遍历当前节点的选择列表得到所有可能的下一节点
对每个节点递归调用函数并输入该节点对应的路径和选择列表
递归调用该函数后，会搜索问题域中的所有可能解，并将合法答案保存下来
而实现该函数的核心难点在于如何正确维护每个节点对应的路径和选择列表
方法也很简单，只需要在递归前更新路径和选择列表，在递归后还原路径和选择列表即可
具体的代码框架如下：
def dfs(路径,选择列表): if 能符合结束条件： 表示当前路径合法，保存当前路径（已经找到正确路径，看要求来决定是否往下走） if 不符合约束条件： 表示当前路径非法，跳过剩下步骤（当前路径已经错误，没必要往下走） for 选择 in 选择列表： 更新路径和选择列表（即做出选择，具体是将当前选择加入路径，将当前选择从选择列表中删除） dfs(路径,选择列表) 还原路径和选择列表（即撤销选择，具体是将当前选择从路径中删除，将当前选择加入选择列表）
