【数据结构DFS】深度优先搜索（Depth-First Search，简称DFS）是图或树结构中常用的一种遍历算法。它通过递归或栈的方式，尽可能深入地访问每个节点，直到无法继续为止，然后回溯到上一个节点，继续探索其他未访问的分支。
DFS在很多实际问题中都有广泛应用，如迷宫求解、拓扑排序、连通性判断等。下面是对DFS的基本原理和应用的总结。
一、DFS基本原理
| 项目 | 内容 |
| 算法类型 | 图/树的遍历算法 |
| 访问方式 | 深度优先，先访问当前节点，再依次访问其子节点 |
| 数据结构 | 栈（递归实现时由系统栈维护） |
| 时间复杂度 | O(V + E)，V为顶点数，E为边数 |
| 空间复杂度 | O(V)（最坏情况下） |
二、DFS实现步骤
1. 选择起始点：从某个节点开始。
2. 标记已访问节点：防止重复访问。
3. 访问当前节点。
4. 递归访问所有未访问的邻接节点。
5. 回溯：当当前节点的所有邻接节点都被访问后，返回上一层。
三、DFS与BFS对比
| 特性 | DFS | BFS |
| 遍历顺序 | 深度优先 | 广度优先 |
| 数据结构 | 栈 | 队列 |
| 是否适合找最短路径 | 否 | 是 |
| 是否适合找所有路径 | 是 | 否 |
| 空间复杂度 | 一般较低 | 可能较高 |
| 应用场景 | 迷宫、连通分量、拓扑排序 | 最短路径、层级遍历 |
四、DFS的应用场景
| 场景 | 说明 |
| 迷宫求解 | 找出从起点到终点的路径 |
| 连通分量 | 判断图中各部分是否连通 |
| 拓扑排序 | 在有向无环图中确定节点顺序 |
| 解决八皇后问题 | 通过回溯寻找合法布局 |
| 图的着色问题 | 为图中的节点分配颜色 |
五、DFS的优缺点
| 优点 | 缺点 |
| 实现简单，易于理解 | 可能导致栈溢出（递归深度大时） |
| 能找到所有可能的路径 | 不适合找最短路径 |
| 占用内存相对较小 | 对于大规模图效率不高 |
综上所述，DFS是一种基础而强大的算法，在处理树和图结构时具有广泛的应用价值。虽然它有自身的局限性，但在许多实际问题中仍是非常有效的工具。