【数据结构DFS】深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着树的深度方向尽可能深入地访问节点，直到到达叶子节点，然后再回溯到上一个节点继续搜索。DFS常用于解决路径查找、连通性问题以及拓扑排序等任务。
DFS原理总结
| 项目 | 内容 |
| 全称 | Depth-First Search |
| 类型 | 遍历算法 |
| 核心思想 | 沿着一条路径尽可能深入，再回溯 |
| 数据结构 | 图或树 |
| 实现方式 | 递归或栈（非递归） |
| 时间复杂度 | O(V + E)，其中 V 是顶点数，E 是边数 |
| 空间复杂度 | O(V)（递归栈深度） |
| 应用场景 | 路径查找、连通性判断、迷宫求解、拓扑排序等 |
DFS与BFS对比
| 特性 | DFS | BFS |
| 访问顺序 | 深度优先 | 广度优先 |
| 使用结构 | 栈（递归） | 队列 |
| 最优性 | 不保证最短路径 | 保证最短路径（在无权图中） |
| 空间效率 | 可能较低（递归深度） | 通常较高（队列存储） |
| 适用情况 | 寻找路径、生成所有可能路径 | 寻找最短路径、层次遍历 |
DFS实现示例（伪代码）
```python
function DFS(node, visited):
if node is not visited:
mark node as visited
for each neighbor of node:
DFS(neighbor, visited)
```
在实际编程中，可以使用递归或显式栈来实现。例如，在Python中可以用`set()`记录已访问节点，避免重复访问。
注意事项
- 在图中，为了避免循环访问，必须维护一个已访问集合。
- DFS适用于稀疏图，而BFS更适合稠密图。
- DFS在某些情况下可能导致栈溢出，尤其在递归深度较大的情况下。
通过合理选择搜索策略，DFS可以在许多实际问题中发挥重要作用。理解其工作原理和应用场景，有助于更高效地设计算法和解决问题。
