深度优先搜索

深度优先搜索

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止（属于盲目搜索）。

搜索顺序为

该算法用逐步加层的方法搜索并且适当时回溯，在每一个已被访问过的节点上标号，以便下次回溯时不会再次被搜索:ABDGEHCFI

深度优先搜索（Depth First Search，简写DFS），简称深搜，其状态“退回一步”的顺序符合“后进先出”的特点，符合“栈”的思想。深搜的空间复杂度较小，因为它只存储了从初始状态到当前状态的一条搜索路径。但是，深搜找到的第一个解不一定是最优解，要找最优解必须搜索整棵“搜索树”。

所以，深搜适用于要求所有解方案的题目。

​ 深搜的特点：递归调用，简单易写。写清终止条件以及调用方式，其他就交给系统吧。不过，系统栈的大小有限制，容易崩溃。因此，有时需要非递归的手工栈。

DFS算法框架（直接递归）

void dfs(int dep，参数表){ 自定义参数； if(当前是目标状态){ 输出解或者作计数、评价处理; }else for(i = 1; i <= 状态的拓展可能数; i++) if(第i种状态拓展可行){ 维护自定义参数; dfs(dep+1,参数表); } }