14.深度优先搜索：一条路走到黑，撞墙就回头

一、什么是深度优先搜索深度优先搜索Depth-First Search简称 DFS是一种经典的图和树的遍历算法它的核心思想是尽可能深地探索每一条路径直到走不通了再回溯换另一条路继续探索。简单来说深度优先搜索就像走迷宫从起点出发选择一个方向一直往前走遇到岔路口就随便选一条路继续深入走到死胡同就退回到上一个岔路口换另一条没走过的路重复这个过程直到找到终点或者所有路都试过了。二、深度优先搜索的核心步骤深度优先搜索的核心步骤可以分为以下几步边界检查判断当前位置是否越界、是否是墙、是否已经走过标记访问将当前位置标记为已访问防止绕圈判断终点如果当前位置是终点返回成功递归探索依次尝试四个方向上、下、左、右递归调用自己回溯如果所有方向都走不通取消当前位置的访问标记返回失败。三、深度优先搜索的代码实现1. Python 版本直观易懂# 方向数组右、下、左、上 dr [0, 1, 0, -1] dc [1, 0, -1, 0] # 迷宫地图0表示通路1表示墙 maze [ [0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1, 1, 0], [0, 1, 0, 0, 0, 0, 1, 0], [0, 1, 0, 1, 1, 0, 1, 0], [0, 1, 0, 1, 0, 0, 1, 0], [0, 1, 0, 1, 0, 1, 1, 0], [0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 1, 1, 1, 0] ] # 访问标记数组 visited [[False for _ in range(8)] for _ in range(8)] # 路径记录 path [] def dfs(row, col): # 1. 边界检查越界、撞墙、走过 if row 0 or row 8 or col 0 or col 8 or maze[row][col] 1 or visited[row][col]: return False # 2. 标记访问 visited[row][col] True path.append((row, col)) # 3. 判断终点右下角是终点 if row 7 and col 7: return True # 4. 递归探索四个方向 for i in range(4): nr row dr[i] nc col dc[i] if dfs(nr, nc): return True # 5. 回溯所有方向都走不通 path.pop() return False # 测试从左上角(0,0)出发 if dfs(0, 0): print(找到路径) for p in path: print(p, end - ) else: print(没有找到路径)2. C 语言版本更贴近底层#include stdio.h #include stdbool.h #define ROWS 8 #define COLS 8 // 方向数组右、下、左、上 int dr[4] {0, 1, 0, -1}; int dc[4] {1, 0, -1, 0}; // 迷宫地图0表示通路1表示墙 int maze[ROWS][COLS] { {0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1, 1, 0}, {0, 1, 0, 0, 0, 0, 1, 0}, {0, 1, 0, 1, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 1, 0}, {0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 1, 1, 1, 0} }; // 访问标记数组 bool visited[ROWS][COLS] {false}; // 路径记录 int path[ROWS * COLS][2]; int pathLen 0; bool dfs(int row, int col) { // 1. 边界检查越界、撞墙、走过 if (row 0 || row ROWS || col 0 || col COLS || maze[row][col] 1 || visited[row][col]) { return false; } // 2. 标记访问 visited[row][col] true; path[pathLen][0] row; path[pathLen][1] col; pathLen; // 3. 判断终点右下角是终点 if (row ROWS - 1 col COLS - 1) { return true; } // 4. 递归探索四个方向 for (int i 0; i 4; i) { int nr row dr[i]; int nc col dc[i]; if (dfs(nr, nc)) { return true; } } // 5. 回溯所有方向都走不通 pathLen--; return false; } int main() { if (dfs(0, 0)) { printf(找到路径\n); for (int i 0; i pathLen; i) { printf((%d, %d), path[i][0], path[i][1]); if (i pathLen - 1) { printf( - ); } } printf(\n); } else { printf(没有找到路径\n); } return 0; }四、深度优先搜索的特点空间复杂度O (深度)因为使用递归调用栈栈的深度等于探索的最大深度时间复杂度O (节点数 边数)因为每个节点和边最多被访问一次路径不一定最短深度优先搜索会先探索一条路到底不一定是最短路径最短路径需要用广度优先搜索BFS。五、深度优先搜索的优化为了提高深度优先搜索的效率可以进行以下优化剪枝提前排除不可能到达终点的路径减少不必要的探索记忆化搜索记录已经探索过的状态避免重复探索迭代实现使用栈代替递归减少递归调用栈的深度避免栈溢出。六、深度优先搜索的实际应用场景深度优先搜索是一种非常基础且重要的算法常见场景包括图和树的遍历遍历图或树的所有节点迷宫问题寻找迷宫的出路排列组合问题生成所有可能的排列组合回溯算法解决八皇后、数独等问题拓扑排序对有向无环图进行拓扑排序连通分量找出图中的所有连通分量。七、深度优先搜索 vs 广度优先搜索深度优先搜索和广度优先搜索是两种最常用的图遍历算法它们的区别如下八、总结深度优先搜索是一种经典的图和树的遍历算法它的核心思想是尽可能深地探索每一条路径直到走不通了再回溯换另一条路继续探索。深度优先搜索的时间复杂度为 O (节点数 边数)空间复杂度为 O (深度)路径不一定最短适合解决排列组合、回溯、连通分量等问题。希望这篇文章能帮助你理解深度优先搜索的原理和实现