DFS算法(深度优先算法)-Python学习

定义：深度优先算法（Depth First Search）属于图算法一种。它的目的是要达到被搜索结构的叶子结点，优先沿着一条搜索路径一直往前走，直到更深的地方搜索失败了，才返回来继续搜索，是一个回溯的过程，因此又叫做回溯算法。

核心思想：就是一条路走到黑，发现彻底没路了，就返回来走另外一条来。属于典型的不撞南墙不回头。不断的往更深的地方搜索，直至失败，再返回来走另外一条路。

算法思路：

栈（先进后出）

1、创建一个空栈stack用来存放节点，和一个空的列表visit来存放已经访问的节点

2、首先将起始点和邻接点放入stack和visit中

3、pop出栈里面最后进入的那个节点，并且从图里面获取这个节点的邻接点

4、如果邻接点不在visit中，就将这个邻接点加入到stack和visit中

5、输出pop出来的节点

6、重复上面的3、4、5步骤，直到栈为空，循环结束

算法实现：

def BFS（参数）：

初始化栈堆stack，visit

初始元素存入栈堆stack，visit

while（栈不空）

｛

pop出栈尾元素

循环找到栈尾元素相邻的又同时没有被处理的节点进行进栈处理，满足条件就进栈并变更状态

可以顺便记录步数以及这个节点的父节点是谁。

｝

五、实现过程：

如图从A开始，使用DFS算法，输出查找路径

1、A首先进栈stack。

stack=A，visit=空

2、接着A出栈，这时候与A相邻的节点B，C，D进栈。

stack=B，C，D

visit=A

3、接着D出栈，与D相邻的A、C、G节点中，G没有进过栈，所以让G进栈stack。

stack=B，C，G

visit=A，D

4、接着G出栈，与G相邻的C、D都已经进过栈中，所以没有元素入栈

stack=B，C

visit=A，B，G

5、接着C出栈，与C相邻的A、D、F、G只有F没有进过栈，所以F入栈

stack=B，F

visit=A，D，G，C

6、接着F出栈，与F相邻的节点均进过栈

stack=B

visit=A，D，G，C，F

7、接着B出栈，相邻的A，F，E只有E未进过栈，所以E入栈

stack=E

visit=A，D，G，C，F，B

8、最后E出栈，与E相邻的B已经进过栈

queue=空

visit=A，D，G，C，F，B，E

至此循环结束，DFS算法也就完成了全部遍历。总体和BFS算法差不多相似，只是BFS采用的队列，先进先出的方式，DFS采用栈，先进后出的方式来实现。

整个算法时间复杂度O（n！）阶乘级算法，效率很低，在数据规模比较大的时候，往往力不从心，也就会出现做题超时等现象。通用的提高效率的解决办法就是剪枝，也就是去除无效的搜索分支。

剪枝常用技巧：

1、优化搜索的顺序

搜索树的不同分层和分支产生的搜索树形态，大小规模差异很大

2、排除等效冗余搜索

如果能提前判断当前节点的不同分支是等效的，就可以只执行一个分支的搜索

3、可行性剪枝

搜索时及时检查状态，如果发现当前分支无法达到边界，马上就执行回溯操作，减少不必要的搜索时间。

4、最优性剪枝

如果在搜索中发现当前分支已经超过了之前获取到的最优解，就马上停止当前分支搜索，执行回溯。

5、记忆化搜索

记录每个状态搜索结果，对于重复遍历的就放弃检索，直接回溯