【数据结构DFS】深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。该算法沿着树的深度方向进行探索，尽可能深入地访问每个节点，直到到达叶子节点，然后回溯到上一个节点继续搜索。
DFS在实际应用中广泛用于解决路径查找、迷宫问题、拓扑排序、连通性检测等问题。其核心思想是通过递归或栈的方式实现对图或树的遍历，确保所有节点都被访问过。
一、DFS的基本原理
DFS的核心在于“深度优先”，即每次选择一个未访问的相邻节点进行深入，直到无法继续为止，再回溯到上一层节点，继续寻找下一个未访问的节点。这种策略使得DFS能够有效地探索整个图的结构。
二、DFS的实现方式
DFS可以通过两种方式实现：
| 实现方式 | 说明 | 优点 | 缺点 |
| 递归方式 | 使用函数递归调用实现 | 代码简洁易懂 | 可能导致栈溢出 |
| 栈方式（迭代） | 使用显式栈结构模拟递归过程 | 避免栈溢出 | 代码稍复杂 |
三、DFS的应用场景
| 应用场景 | 说明 |
| 图的遍历 | 遍历所有节点，检查连通性 |
| 寻找路径 | 在有向图中寻找从起点到终点的路径 |
| 拓扑排序 | 对有向无环图进行拓扑排序 |
| 迷宫求解 | 找到迷宫中的出口路径 |
| 生成所有可能的组合 | 如排列、组合问题的求解 |
四、DFS与BFS的对比
| 特性 | DFS | BFS |
| 遍历顺序 | 深度优先 | 广度优先 |
| 存储结构 | 栈 | 队列 |
| 内存使用 | 一般较小 | 一般较大 |
| 是否适合找到最短路径 | 不一定 | 是 |
| 适用情况 | 探索所有可能路径 | 找到最短路径或最小步数 |
五、DFS的优缺点
| 优点 | 缺点 |
| 能够找到所有可能的路径 | 可能会陷入无限循环（如图中有环） |
| 实现简单，易于理解 | 空间复杂度较高（特别是递归方式） |
| 适用于搜索空间较大的情况 | 不能保证找到最优解（如最短路径） |
六、总结
DFS是一种基础且重要的图遍历算法，适用于多种数据结构和问题类型。尽管它在某些情况下不如广度优先搜索高效，但其在探索性和灵活性方面具有独特优势。在实际编程中，应根据具体需求选择合适的实现方式，并注意处理环路和重复访问的问题。掌握DFS的原理和应用场景，有助于提升算法设计能力和问题解决能力。