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

背景

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 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0

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

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

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

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

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

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

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

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

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

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

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

代码

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)

变更出口位置

>>>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)

递归的回溯过程

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

在代码中添加增加埋点，使每次发生递归时，对参数（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）往右走到（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)

第七步：（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)

第十四步：（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)

第十七步：（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，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博客