您现在的位置是：首页 > 其他

当前栏目

（DFS）深度优先搜索算法详解

算法

2023-04-18 16:30:03 时间

背景

DFS 英文全称为（Depth First Search），中文简称深度优先搜索算法，其过程为沿着每一个可能的路径向下进行搜索，直到不能再深入为止，并且每一个节点只能访问一次。

算法的搜索遍历图的步骤

（1）首先找到初始节点A，

（2）依此从A未被访问的邻接点出发，对图进行深度优先遍历

（3）若有节点未被访问，则回溯到该节点，继续进行深度优先遍历

（4）直到所有与顶点A路径想通的节点都被访问过一次

举个例子，在下方的无向连通图中，假设我们要从起始点A出发，使用深度优先搜索算法进行搜索，首先访问A->B->E，走不通了，回溯到A起始点，走第二个分支节点B，路径为A->C->F->H->G->D，走不通了，再回溯到起始点A，发现所有的节点都已经走过一次了，因此本次搜索结束。

DFS的应用

深度优先搜索算法常常被用于解决迷宫问题。

首先我们定义一个5*5的迷宫矩阵 maze

其中0代表迷宫走可以走的路，1代表迷宫中的墙壁

要求从左上角出发，走到左下角结束（0，0）出发，走到（4，4）

我们使用深度优先搜索算法进行求解

（1）从起始点（0，0）出发，第一步只能往下走（1，0），第二步走到交叉路口（2，0）

1	0	0
1	1	1
0	0	0
1	1	1
0	0	1

（2）由于出口在右下角，设定优先顺序，下>右>左>上

（3）走到（2，0）处开始往下走，直到走到（4，2）发现走不通

1	0	0
1	1	1
0	0	0
1	1	1
0	0	1

（4）此时回溯到上一节点（2，0），开始沿着另一个分支进行深度优先搜索

1	0	0
1	1	1
0	0	0
1	1	1
0	0	1

（5）在节点（2，4）中再次遇到分支，优先往下走，最终走到（4，4）走出迷宫

1	0	0
1	1	1
0	0	0
1	1	1
0	0	1

（6）因此最终走出迷宫的路径为：

(0,0)->(1,0)->(2,0)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)

（6）假设迷宫的出口在（2，0），则回溯到最近的未走过的分支顶点（2，4）往上走，最终走到终点

1	0	0
1	1	1
0	0	0
1	1	1
0	0	1

代码

def DFS(x, y):
    if x <0 or x >= len(maze) or y < 0 or y >= len(maze[0]):#走出了迷宫墙外，不合法
        return False
    if maze_visit[x][y] == True:#防止走回头
        return False
    if maze[x][y] == 1:#标记为1的不能走
        return False
    maze_visit[x][y] = True#标记本次递归路线，防止走回头
    if x == N and y == M:#走到终点停止递归
        myStack.append((x,y))
        return True
    for m in move:#四个方向尝试走
        next_x = x+m[0]
        next_y = y+m[1]
        if DFS(next_x, next_y):#判断能不能走通，能走通继续下一步递归
            myStack.append((x,y))#将走通的路径记录下来
            return True
    return False
 
maze = [[0, 1, 0, 0, 0],
        [0, 1, 1, 1, 0],
        [0, 0, 0, 0, 0],
        [0, 1, 1, 1, 0],
        [0, 0, 0, 1, 0]]#定义迷宫
maze_visit = [[False, False, False, False, False],
              [False, False, False, False, False],
              [False, False, False, False, False],
              [False, False, False, False, False],
              [False, False, False, False, False]]#记录路线是否已经走过，防止走反

move = [(0,1), (0,-1), (1,0), (-1,0)] #定义四个方向走的顺序
N, M = 4, 4 #定义出口的位置
myStack = []#记录走通的路径
DFS(0,0)#递归求解
myStack = myStack[::-1]#反转列表
for row in myStack:
    print('(' + str(row[0]) + ','+ str(row[1]) + ')')

输出迷宫路线

>>>move = [(0,1), (0,-1), (1,0), (-1,0)] #定义四个方向走的顺序
>>>N, M = 4, 4 #定义出口的位置
>>>myStack = []#记录走通的路径
>>>DFS(0,0)#递归求解
>>>myStack = myStack[::-1]#反转列表
>>>for row in myStack:
...    print('(' + str(row[0]) + ','+ str(row[1]) + ')')
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)

1	0	0
1	1	1
0	0	0
1	1	1
0	0	1

变更出口位置

>>>move = [(0,1), (0,-1), (1,0), (-1,0)] #定义四个方向走的顺序
>>>N, M = 0, 2 #定义出口的位置
>>>myStack = []#记录走通的路径
>>>DFS(0,0)#递归求解
>>>myStack = myStack[::-1]#反转列表
>>>for row in myStack:
...    print('(' + str(row[0]) + ','+ str(row[1]) + ')')
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(1,4)
(0,4)
(0,3)
(0,2)

1	0	0
1	1	1
0	0	0
1	1	1
0	0	1

递归的回溯过程

以入口为（0，0），出口为（0，2）为例，详细说一下递归的回溯过程

1	0	0
1	1	1
0	0	0
1	1	1
0	0	1

在代码中添加增加埋点，使每次发生递归时，对参数（x，y）进行输出

def DFS(x, y):
    print("end:", str((x, y)))
    if x <0 or x >= len(maze) or y < 0 or y >= len(maze[0]):#走出了迷宫墙外，不合法
        print("False: 走出了迷宫墙外，不合法")
        return False
    if maze_visit[x][y] == True:#防止走回头
        print("False: 往回走，不合法")
        return False
    if maze[x][y] == 1:#标记为1的不能走
        print("False: 穿墙，不合法")
        return False
    maze_visit[x][y] = True#标记本次递归路线，防止走回头
    if x == N and y == M:#走到终点停止递归
        print("True: 到达终点")
        myStack.append((x,y))
        return True
    for m in move:#四个方向尝试走
        print("strat:", str((x,y)), "move:", str(m))
        next_x = x+m[0]
        next_y = y+m[1]
        if DFS(next_x, next_y):#判断能不能走通，能走通继续下一步递归
            myStack.append((x,y))#将走通的路径记录下来
            return True
        print("回溯上一节点")
    return False

创建好埋点后执行代码，输出如下：

>>>maze = [[0, 1, 0, 0, 0],
...        [0, 1, 1, 1, 0],
...        [0, 0, 0, 0, 0],
...        [0, 1, 1, 1, 0],
...        [0, 0, 0, 1, 0]]#定义迷宫
>>>maze_visit = [[False, False, False, False, False],
...              [False, False, False, False, False],
...              [False, False, False, False, False],
...              [False, False, False, False, False],
...              [False, False, False, False, False]]#记录路线是否已经走过，防止走反
>>>move = [(0,1), (0,-1), (1,0), (-1,0)] #定义四个方向走的顺序
>>>N, M = 0, 2 #定义出口的位置
>>>myStack = []#记录走通的路径
>>>DFS(0,0)#递归求解
end: (0, 0)
strat: (0, 0) move: (0, 1)
end: (0, 1)
False: 穿墙，不合法
回溯上一节点
strat: (0, 0) move: (0, -1)
end: (0, -1)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (0, 0) move: (1, 0)
end: (1, 0)
strat: (1, 0) move: (0, 1)
end: (1, 1)
False: 穿墙，不合法
回溯上一节点
strat: (1, 0) move: (0, -1)
end: (1, -1)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (1, 0) move: (1, 0)
end: (2, 0)
strat: (2, 0) move: (0, 1)
end: (2, 1)
strat: (2, 1) move: (0, 1)
end: (2, 2)
strat: (2, 2) move: (0, 1)
end: (2, 3)
strat: (2, 3) move: (0, 1)
end: (2, 4)
strat: (2, 4) move: (0, 1)
end: (2, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (2, 4) move: (0, -1)
end: (2, 3)
False: 往回走，不合法
回溯上一节点
strat: (2, 4) move: (1, 0)
end: (3, 4)
strat: (3, 4) move: (0, 1)
end: (3, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (3, 4) move: (0, -1)
end: (3, 3)
False: 穿墙，不合法
回溯上一节点
strat: (3, 4) move: (1, 0)
end: (4, 4)
strat: (4, 4) move: (0, 1)
end: (4, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (4, 4) move: (0, -1)
end: (4, 3)
False: 穿墙，不合法
回溯上一节点
strat: (4, 4) move: (1, 0)
end: (5, 4)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (4, 4) move: (-1, 0)
end: (3, 4)
False: 往回走，不合法
回溯上一节点
回溯上一节点
strat: (3, 4) move: (-1, 0)
end: (2, 4)
False: 往回走，不合法
回溯上一节点
回溯上一节点
strat: (2, 4) move: (-1, 0)
end: (1, 4)
strat: (1, 4) move: (0, 1)
end: (1, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (1, 4) move: (0, -1)
end: (1, 3)
False: 穿墙，不合法
回溯上一节点
strat: (1, 4) move: (1, 0)
end: (2, 4)
False: 往回走，不合法
回溯上一节点
strat: (1, 4) move: (-1, 0)
end: (0, 4)
strat: (0, 4) move: (0, 1)
end: (0, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (0, 4) move: (0, -1)
end: (0, 3)
strat: (0, 3) move: (0, 1)
end: (0, 4)
False: 往回走，不合法
回溯上一节点
strat: (0, 3) move: (0, -1)
end: (0, 2)
True: 到达终点

接下来详细对每一步进行解析，先看方向依次为：右>左>下>上

move = [(0,1), (0,-1), (1,0), (-1,0)]

第一步：（0，0）往右走到（0，1）穿墙，不合法，回溯到（0，0）

第二步：（0，0）往左走到（0，-1）走出了迷宫墙外，不合法，回溯到（0，0）

第三步：（0，0）往下走到（1，0）合法，将（1，0）作为起点，进入DFS（1，0）

end: (0, 0)
strat: (0, 0) move: (0, 1)
end: (0, 1)
False: 穿墙，不合法
回溯上一节点
strat: (0, 0) move: (0, -1)
end: (0, -1)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (0, 0) move: (1, 0)
end: (1, 0)

1	0	0
1	1	1
0	0	0
1	1	1
0	0	1

第四步：（1，0）往右走到（1，1）穿墙，不合法，回溯到（1，0）

第五步：（1，0）往左走到（1，-1）走出了迷宫墙外，不合法，回溯到（1，0）

第六步：（1，0）往下走到（1，0）合法，将（2，0）作为起点，进入DFS（2，0）

strat: (1, 0) move: (0, 1)
end: (1, 1)
False: 穿墙，不合法
回溯上一节点
strat: (1, 0) move: (0, -1)
end: (1, -1)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (1, 0) move: (1, 0)
end: (2, 0)

1	0	0
1	1	1
0	0	0
1	1	1
0	0	1

第七步：（2，0）往右走到（2，1）合法，将（2，1）作为起点，进入DFS（2，1）

第八步：（2，1）往右走到（2，2）合法，将（2，2）作为起点，进入DFS（2，2）

第九步：（2，2）往右走到（2，3）合法，将（2，3）作为起点，进入DFS（2，3）

第十步：（2，3）往右走到（2，4）合法，将（2，4）作为起点，进入DFS（2，4）

第十一步：（2，4）往右走到（2，5）走出了迷宫墙外，不合法，回溯到（2，4）

第十二步：（2，4）往左走到（2，3）往回走，不合法，回溯到（2，4）

第十三步：（2，4）往下走到（3，4）合法，将（3，4）作为起点，进入DFS（3，4）

strat: (2, 0) move: (0, 1)
end: (2, 1)
strat: (2, 1) move: (0, 1)
end: (2, 2)
strat: (2, 2) move: (0, 1)
end: (2, 3)
strat: (2, 3) move: (0, 1)
end: (2, 4)
strat: (2, 4) move: (0, 1)
end: (2, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (2, 4) move: (0, -1)
end: (2, 3)
False: 往回走，不合法
回溯上一节点
strat: (2, 4) move: (1, 0)
end: (3, 4)

1	0	0
1	1	1
0	0	0
1	1	1
0	0	1

第十四步：（3，4）往右走到（3，5）走出了迷宫墙外，不合法，回溯到（3，4）

第十五步：（3，4）往左走到（3，3）往回走，不合法，回溯到（3，4）

第十六步：（3，4）往下走到（4，4）合法，将（4，4）作为起点，进入DFS（4，4）

strat: (3, 4) move: (0, 1)
end: (3, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (3, 4) move: (0, -1)
end: (3, 3)
False: 穿墙，不合法
回溯上一节点
strat: (3, 4) move: (1, 0)
end: (4, 4)

1	0	0
1	1	1
0	0	0
1	1	1
0	0	1

第十七步：（4，4）往右走到（4，5）走出了迷宫墙外，不合法，回溯到（4，4）

第十八步：（4，4）往左走到（4，3）穿墙，不合法，回溯到（4，4）

第十九步：（4，4）往下走到（4，4）走出了迷宫墙外，不合法，回溯到（4，4）

第十九步：（4，4）往上走到（3，4）往回走，不合法，回溯到（4，4）

第二十步：此时四个方向都走不通，因此回溯到上一个交叉路口（3，4），在第十四到第十八步（3，4）节点已经往右，左，下三个方向走过一次了（move循环到了第三位），因此只剩往上走一种选择，（3，4）往上走到（2，4）往回走，不合法，回溯到（2，4）

第二十一步：同理（2，4）在第十一到第十三步已经往右，左，下三个方向走过一次了，因此只剩往上走一种选择，（3，4）往上走到（1，4），合法，将（1，4）作为起点，进入DFS（1，4）

strat: (4, 4) move: (0, 1)
end: (4, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (4, 4) move: (0, -1)
end: (4, 3)
False: 穿墙，不合法
回溯上一节点
strat: (4, 4) move: (1, 0)
end: (5, 4)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (4, 4) move: (-1, 0)
end: (3, 4)
False: 往回走，不合法
回溯上一节点
回溯上一节点
strat: (3, 4) move: (-1, 0)
end: (2, 4)
False: 往回走，不合法
回溯上一节点
回溯上一节点
strat: (2, 4) move: (-1, 0)
end: (1, 4)

1	0	0
1	1	1
0	0	0
1	1	1
0	0	1

从（1，4）开始到达终点的步骤再次就不进行详细解析了～～～（同理）最终到达终点（0，2）

strat: (1, 4) move: (0, 1)
end: (1, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (1, 4) move: (0, -1)
end: (1, 3)
False: 穿墙，不合法
回溯上一节点
strat: (1, 4) move: (1, 0)
end: (2, 4)
False: 往回走，不合法
回溯上一节点
strat: (1, 4) move: (-1, 0)
end: (0, 4)
～～～～～～～～～～～～～～～～～～～～
strat: (0, 4) move: (0, 1)
end: (0, 5)
False: 走出了迷宫墙外，不合法
回溯上一节点
strat: (0, 4) move: (0, -1)
end: (0, 3)
～～～～～～～～～～～～～～～～～～～～
strat: (0, 3) move: (0, 1)
end: (0, 4)
False: 往回走，不合法
回溯上一节点
strat: (0, 3) move: (0, -1)
end: (0, 2)
True: 到达终点

！！！！！！！！！！！！！！！！！！递归结束！！！！！！！！！！！！！！！！！！！！

使用递归求解的案例

匈牙利算法寻找最大匹配_202xxx的博客-CSDN博客

【牛客网华为机试】HJ28 素数伴侣_202xxx的博客-CSDN博客

【牛客网华为机试】HJ43 迷宫问题_202xxx的博客-CSDN博客

猜你喜欢

文件写入的6种方法，这种方法性能最好
作为程序员的基本素养，你了解Python变量引用吗
Android PDF开发：android-pdfview
本地生活服务
Flutter漫说：组件生命周期、State状态管理及局部重绘的实现（Inherit）
嗯，查询滑动窗口最大值的这4种方法不错...
Jetpack：使用 ActivityResult 处理 Activity 之间的数据通信
领导：谁再用定时任务实现关闭订单，立马滚蛋！
lombok中的builder注解居然是一种设计模式：让我们了解一下实用的“建造者模式”吧
小白学算法：买卖股票的最佳时机！
Flutter 中的Error的捕获及处理
Flutter：Navigator2.0介绍及使用
Java中的5大队列，你知道几个？
RecyclerView局部刷新机制——payload
免费代理IP – 免费HTTP代理IP_SOCKS5代理服务器_优质IP代理
一文详解「队列」，手撸队列的3种方法！
IntentService详解
解决Webview加载不完全导致部分js无效
最新版MySQL在MacOS上的安装与使用！
实现一个通用的中英文排序工具

zl程序教程