【数据结构DFS】深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着树的深度方向尽可能深入地探索，直到到达叶子节点，然后再回溯到上一个节点继续探索其他分支。DFS广泛应用于图的遍历、路径查找、拓扑排序、连通性检测等场景。
DFS基本思想
DFS的核心思想是“深入探索”，通过递归或栈的方式实现。在每一步中，选择一个未访问的相邻节点进行访问，并重复该过程，直到无法继续前进为止。此时，回退到上一个节点，继续探索其他可能的路径。
DFS的实现方式
DFS可以通过两种主要方式实现：
| 实现方式 | 描述 | 优点 | 缺点 |
| 递归 | 使用函数递归调用自身来实现 | 代码简洁，易于理解 | 可能导致栈溢出，不适合大规模数据 |
| 栈（迭代） | 使用显式栈结构模拟递归过程 | 避免栈溢出问题，适合大规模数据 | 代码复杂度较高 |
DFS的应用场景
| 应用场景 | 说明 |
| 图的遍历 | 遍历所有节点，检查连通性 |
| 寻找路径 | 在图中寻找从起点到终点的路径 |
| 拓扑排序 | 对有向无环图进行排序 |
| 迷宫求解 | 在迷宫中找到出口 |
| 解决数独 | 通过尝试不同的数字组合解决问题 |
DFS与BFS对比
| 特性 | DFS | BFS |
| 探索方向 | 深度方向 | 广度方向 |
| 数据结构 | 栈 | 队列 |
| 空间复杂度 | O(h)（h为树高） | O(n)（n为节点数） |
| 是否能找到最短路径 | 否 | 是 |
| 适用场景 | 路径查找、连通性 | 最短路径、层次遍历 |
总结
DFS是一种基础且重要的图遍历算法，适用于多种实际问题的解决。尽管其在某些情况下可能不如广度优先搜索高效，但其简洁的实现方式和灵活的应用范围使其在数据结构和算法领域中占据重要地位。无论是递归还是迭代实现，掌握DFS对于理解和应用更复杂的算法具有重要意义。
