欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

DFS——深度优先算法(Depth First Search)

程序员文章站 2022-05-22 21:17:52
...

1、前言

这几天刷leetcode经常碰到DFS BFS的问题,之前一直也是模棱两可,凭着感觉做,是需要总结一下了。

深度优先搜索(缩写DFS)是一种在开发爬虫早期使用较多的方法。属于图算法的一种,也是对一个连通图进行遍历的算法。其思想是:从一个顶点v开始,沿着一条路线一直走到底,如果发现不能到达目标,那就返回到走不通节点的上一个节点,然后尝试从另一条路开始走到底,每个节点只可以访问一次。这种尽量往深处走的概念即是深度优先的概念。

2、DFS的基本思路

深度优先遍历图的方法是:从图中某顶点v出发:
(1)访问顶点v

(2)依次v的未被访问的邻接点(adjacent)出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;

(3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。 当然,当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法,那就是广度优先搜索(BFS).

3、DFS特点以及和BFS的比较

  • DFS可以用递归来写,也可以用来写。

  • DFS在回溯时要取消原先的标记,而BFS不存在回溯也就不存在取消标记这一问题。(即避免节点出现在别的搜索路径中)

  • DFS难以寻找最优解,仅仅只能寻找有解。其优点就是相比BFS内存消耗小


也许你会问,为什么BFS会消耗大量内存?

我们假设每一个节点衍生出来的邻接点(adjacent)平均的个数是N个,那么当起点开始搜索的时候,队列有一个节点,当起点拿出来后,把它所有相邻的节点放进去,那么队列就有N个节点,当下一层的搜索中再加入元素到队列的时候,节点数达到了N2,你可以想想,一旦N是一个比较大的数的时候,这个树的层次又比较深,那这个队列就得需要很大的内存空间了。

于是广度优先搜索的缺点出来了:在树的层次较深&子节点数较多的情况下,消耗内存十分严重。广度优先搜索适用于节点的子节点数量不多,并且树的层次不会太深的情况。

而深度优先搜索则是一条道走到黑出现不满足条件的就回溯,而出现满足条件的就继续,虽然最差情况下,消耗的时间和BFS差不多,但是空间复杂度大大降低,而且一般情况下不会出现最差情况···

4、深度优先搜索

4.1 举例

(ps:本例借鉴自rapheal的博客
如下图所示,求从图中的V0(顶点)出发,是否存在一条路径长度为4的搜索路径。
DFS——深度优先算法(Depth First Search)

显然,直观看出:V0->V3->V5->V6。

4.2 处理过程

DFS——深度优先算法(Depth First Search)
DFS——深度优先算法(Depth First Search)
DFS——深度优先算法(Depth First Search)
DFS——深度优先算法(Depth First Search)
DFS——深度优先算法(Depth First Search)
DFS——深度优先算法(Depth First Search)
DFS——深度优先算法(Depth First Search)
DFS——深度优先算法(Depth First Search)
DFS——深度优先算法(Depth First Search)
DFS——深度优先算法(Depth First Search)

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函数的调用堆栈

图片有些错误(V0V1后面的数字应该都加1)

DFS——深度优先算法(Depth First Search)
此后堆栈调用返回到V0那一层,因为V1那一层也找不到跟V1的相邻未访问节点。

DFS——深度优先算法(Depth First Search)
此后堆栈调用返回到V3那一层。

DFS——深度优先算法(Depth First Search)
堆栈调用返回到V3那一层后,依次找到V5V6。满足条件,退出。

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个数,只允许加法减法运算。我绘制了如下图的搜索树。

DFS——深度优先算法(Depth First Search)

此处只有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]

相关标签: 算法 leetcode