DFS——深度优先算法（Depth First Search）
1、前言
这几天刷leetcode经常碰到DFS BFS的问题，之前一直也是模棱两可，凭着感觉做，是需要总结一下了。
深度优先搜索（缩写DFS）是一种在开发爬虫早期使用较多的方法。属于图算法的一种，也是对一个连通图进行遍历的算法。其思想是：从一个顶点vv开始，沿着一条路线一直走到底，如果发现不能到达目标，那就返回到走不通节点的上一个节点，然后尝试从另一条路开始走到底，每个节点只可以访问一次。这种尽量往深处走的概念即是深度优先的概念。
2、DFS的基本思路
深度优先遍历图的方法是:从图中某顶点vv出发：
（1）访问顶点vv；
（2）依次从vv的未被访问的邻接点(adjacentadjacent)出发，对图进行深度优先遍历；直至图中和vv有路径相通的顶点都被访问；
（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。 当然，当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法，那就是广度优先搜索(BFS).
3、DFS特点以及和BFS的比较
DFS可以用递归来写，也可以用栈来写。
DFS在回溯时要取消原先的标记，而BFS不存在回溯也就不存在取消标记这一问题。(即避免节点出现在别的搜索路径中)
DFS难以寻找最优解，仅仅只能寻找有解。其优点就是相比BFS内存消耗小
也许你会问，为什么BFS会消耗大量内存？
我们假设每一个节点衍生出来的邻接点(adjacentadjacent)平均的个数是NN个，那么当起点开始搜索的时候，队列有一个节点，当起点拿出来后，把它所有相邻的节点放进去，那么队列就有N个节点，当下一层的搜索中再加入元素到队列的时候，节点数达到了N2N2，你可以想想，一旦NN是一个比较大的数的时候，这个树的层次又比较深，那这个队列就得需要很大的内存空间了。
于是广度优先搜索的缺点出来了：在树的层次较深&子节点数较多的情况下，消耗内存十分严重。广度优先搜索适用于节点的子节点数量不多，并且树的层次不会太深的情况。
而深度优先搜索则是一条道走到黑，出现不满足条件的就回溯，而出现满足条件的就继续，虽然最差情况下，消耗的时间和BFS差不多，但是空间复杂度大大降低，而且一般情况下不会出现最差情况···
4、深度优先搜索
4.1 举例
（ps：本例借鉴自rapheal的博客）
如下图所示，求从图中的V0V0（顶点）出发，是否存在一条路径长度为4的搜索路径。
显然，直观看出：V0->V3->V5->V6。
4.2 处理过程
4.3 处理过程伪代码（python 3.x）
# coding: UTF-8
'''
DFS核心伪代码(递归写法)
前置条件是visited列表，没处理的加进去，处理完的扔掉
param nodes 当前开始搜索的节点
param depth 当前到达的深度，也即是路径长度
return 是否有解
'''
class Node(object):
def __init__(self, val, nextNodes):
self.val = val
self.nextNodes = nextNodes
visited = []
def dfs(nodes, depth):
# 路径长度满足要求，表示此次搜索有解
if depth == 4:
return True
# 遍历跟节点n相邻的节点nextNode
for n in nodes.nextNodes:
# 例如搜索到V1了，那么V1要设置成已访问
if n not in visited:
visited.append(n)
# 如果搜索出有解
# 例如到了V6，找到解了，
# 你必须一层一层递归的告诉上层已经找到解
if dfs(n, depth+1):
return True
# 重新设置成未访问，因为它有可能出现在下一次搜索的路径中
visited.remove(n)
# 本次搜索无解
return False
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
4.4 DFS函数的调用堆栈
图片有些错误(V0V0、V1V1后面的数字应该都加1)
此后堆栈调用返回到V0V0那一层，因为V1V1那一层也找不到跟V1V1的相邻未访问节点。
此后堆栈调用返回到V3V3那一层。
堆栈调用返回到V3V3那一层后，依次找到V5V5和V6V6。满足条件，退出。
5、24点算法
5.1 题目描述
想必大家都玩过一个游戏，叫做“24点”：给出4个整数，要求用加减乘除4个运算使其运算结果变成24，4个数字要不重复的用到计算中。
例如给出4个数：1、2、3、4。我可以用以下运算得到结果24：
1*2*3*4 = 24；2*3*4/1 = 24；(1+2+3)*4=24；……
如上，是有很多种组合方式使得他们变成24的，当然也有无法得到结果的4个数，例如：1、1、1、1。
现在我给你这样4个数，你能告诉我它们能够通过一定的运算组合之后变成24吗？这里我给出约束：数字之间的除法中不得出现小数，例如原本我们可以1/4=0.25，但是这里的约束指定了这样操作是不合法的。
5.2 解法：搜索树
思路是把结构转换成树形结构来做。
这里为了方便叙述，我假设现在只有3个数，只允许加法减法运算。我绘制了如下图的搜索树。
此处只有3个数并且只有加减法，所以第二层的节点最多就6个，如果是给你4个数并且有加减乘除，那么第二层的节点就会比较多了，当延伸到第三层的时候节点数就比较多了，使用BFS的缺点就暴露了，需要很大的空间去维护那个队列。而你看这个搜索树，其实第一层是3个数，到了第二层就变成2个数了，也就是递归深度其实不会超过3层，所以采用DFS来做会更合理，平均效率要比BFS快。
python代码如下：
# author：samuel ko
# 2017.7.21
'''
24点 dfs算法
lst是存放4个数的列表（数组）
des为目标
'''
def dfs(lst, des):
if des == 24 and len(lst) == 0:
return True
for i in range(len(lst)):
lst1 = lst[:i] + lst[i + 1:]
# 初始状态
if len(lst) == 4:
if dfs(lst1, lst[i]):
return True
else:
if dfs(lst1, des+lst[i]):
return True
if dfs(lst1, des*lst[i]):
return True
if des > lst[i]:
if dfs(lst1, des-lst[i]):
return True
elif lst[i] > des:
if dfs(lst1, lst[i]-des):
return True
if des / lst[i] > 1:
if dfs(lst1, des/lst[i]):
return True
elif lst[i] / des > 1:
if dfs(lst1, lst[i]/des):
return True
return False
if __name__ == "__main__":
a = dfs([5,2,4,100], 0)
print(a)- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
7、总结
DFS适合此类题目：给定初始状态跟目标状态，要求判断从初始状态到目标状态是否有解。
参考资料
1、[rapheal的博客]: [http://rapheal.iteye.com/blog/1526863]
2、[DFS(wikipedia)]: [https://en.wikipedia.org/wiki/DFS]
上一篇： 图的理解：深度优先和广度优先遍历
下一篇： 关于阶段
推荐阅读
-
可能是目前为止最为详细的深度优先搜索DFS和广度优先搜索BFS算法分析
-
数据结构与算法-----BFS与DFS（广度优先搜索与深度优先搜索）
-
数据结构与算法_深度优先搜索（DFS）与广度优先搜索（BFS）详解
-
Java数据结构与算法：图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现
-
BFS（广度优先搜索算法）和DFS（深度优先搜索算法）
-
数据结构与算法————图的遍历DFS深度优先搜索和BFS广度优先搜索
-
【算法】广度优先搜索（BFS）和深度优先搜索（DFS）
-
PHP实现广度优先搜索算法(BFS,Broad First Search)详解
-
PHP实现深度优先搜索算法(DFS,Depth First Search)详解
-
python实现图的深度优先搜索(DFS)和广度优先搜索(BFS)算法及Dijkstra最短路径应用