【数据结构DFS】深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着每个分支尽可能深入地探索，直到到达叶子节点或无法继续前进为止，然后回溯到上一个节点，继续探索其他未访问的分支。
DFS在实际应用中广泛用于解决路径查找、连通性问题、拓扑排序、迷宫求解等问题。其核心思想是递归或栈实现，通过访问节点后标记为已访问，防止重复访问。
一、DFS的基本原理
1. 初始状态：选择一个起始节点作为起点。
2. 访问节点：访问当前节点，并将其标记为已访问。
3. 递归探索：对当前节点的所有邻接节点进行DFS遍历。
4. 回溯：当所有邻接节点都被访问过之后，返回上一层节点，继续处理。
二、DFS的实现方式
| 实现方式 | 描述 | 是否需要额外数据结构 |
| 递归实现 | 使用函数递归调用自身来实现，逻辑清晰 | 需要系统栈支持 |
| 栈实现（非递归） | 使用显式栈模拟递归过程，避免栈溢出 | 需要手动维护栈 |
三、DFS的应用场景
| 应用场景 | 说明 |
| 图的连通性检测 | 判断图中两个节点是否连通 |
| 网络爬虫 | 深度爬取网页内容 |
| 迷宫求解 | 找到从起点到终点的路径 |
| 拓扑排序 | 对有向无环图进行排序 |
| 存在性问题 | 如八皇后问题、数独等 |
四、DFS的优缺点
| 优点 | 缺点 |
| 实现简单，逻辑清晰 | 可能会陷入无限循环（如存在环） |
| 能找到一条路径 | 不一定是最短路径 |
| 占用内存较少（相对BFS） | 在某些情况下效率较低 |
五、DFS与BFS对比
| 特性 | DFS | BFS |
| 遍历顺序 | 深度优先 | 广度优先 |
| 数据结构 | 栈 | 队列 |
| 最短路径 | 不保证 | 保证 |
| 内存占用 | 较低 | 较高 |
| 适用场景 | 寻找路径、连通性 | 最短路径、层次遍历 |
六、总结
DFS是一种基础且重要的算法，适用于多种数据结构的遍历和搜索任务。虽然它在某些情况下可能不如BFS高效，但其简洁性和灵活性使其在实际编程中仍然具有重要地位。掌握DFS的实现方式和应用场景，有助于提升算法思维和解决问题的能力。
