DFS——深度优先算法(Depth First Search)
1、前言
这几天刷leetcode经常碰到DFS BFS的问题,之前一直也是模棱两可,凭着感觉做,是需要总结一下了。
深度优先搜索(缩写DFS)是一种在开发爬虫早期使用较多的方法。属于图算法的一种,也是对一个连通图进行遍历的算法。其思想是:从一个顶点
2、DFS的基本思路
深度优先遍历图的方法是:从图中某顶点
(1)访问顶点
(2)依次从
(3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。 当然,当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法,那就是广度优先搜索(BFS).
3、DFS特点以及和BFS的比较
DFS可以用递归来写,也可以用栈来写。
DFS在回溯时要取消原先的标记,而BFS不存在回溯也就不存在取消标记这一问题。(即避免节点出现在别的搜索路径中)
DFS难以寻找最优解,仅仅只能寻找有解。其优点就是相比BFS内存消耗小
也许你会问,为什么BFS会消耗大量内存?
我们假设每一个节点衍生出来的邻接点(
于是广度优先搜索的缺点出来了:在树的层次较深&子节点数较多的情况下,消耗内存十分严重。广度优先搜索适用于节点的子节点数量不多,并且树的层次不会太深的情况。
而深度优先搜索则是一条道走到黑,出现不满足条件的就回溯,而出现满足条件的就继续,虽然最差情况下,消耗的时间和BFS差不多,但是空间复杂度大大降低,而且一般情况下不会出现最差情况···
4、深度优先搜索
4.1 举例
(ps:本例借鉴自rapheal的博客)
如下图所示,求从图中的
显然,直观看出: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
4.4 DFS函数的调用堆栈
图片有些错误(
V0 、V1 后面的数字应该都加1)
此后堆栈调用返回到
此后堆栈调用返回到
堆栈调用返回到
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)
7、总结
DFS适合此类题目:给定初始状态跟目标状态,要求判断从初始状态到目标状态是否有解。
参考资料
1、[rapheal的博客]: [http://rapheal.iteye.com/blog/1526863]
2、[DFS(wikipedia)]: [https://en.wikipedia.org/wiki/DFS]
上一篇: URL编码
下一篇: nginx中的脚本(理论篇)
推荐阅读
-
可能是目前为止最为详细的深度优先搜索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最短路径应用