【数据结构DFS】深度优先搜索（Depth-First Search，简称DFS）是图或树结构中常用的一种遍历算法。它从起始节点出发，沿着一条路径尽可能深入地访问每个节点，直到到达无法继续前进的终点，然后回溯到上一个节点，继续探索其他未访问的分支。DFS常用于解决路径查找、连通性判断、拓扑排序等问题。
DFS核心思想
DFS通过递归或栈的方式实现，其基本步骤如下：
1. 选择一个起始点，标记为已访问。
2. 访问该节点的所有邻接节点（在图中）或子节点（在树中）。
3. 对每个未访问的邻接/子节点递归执行DFS。
4. 当所有邻接/子节点都被访问后，回溯到上一个节点，继续处理下一个可能的分支。
DFS特点总结
| 特点 | 描述 |
| 遍历方式 | 深度优先，先深入再回溯 |
| 数据结构 | 使用栈（显式或隐式递归栈） |
| 空间复杂度 | O(h)，h为树的高度或图的深度 |
| 时间复杂度 | O(V + E)，V为顶点数，E为边数 |
| 应用场景 | 寻找路径、检测环、连通分量、拓扑排序等 |
| 是否可重复访问 | 通常需要标记已访问节点，避免重复 |
DFS与BFS对比
| 项目 | DFS | BFS |
| 遍历顺序 | 深度优先 | 层次优先 |
| 数据结构 | 栈 | 队列 |
| 最优解 | 不保证最短路径 | 保证最短路径（在无权图中） |
| 空间复杂度 | 较低（适合深图） | 可能较高（适合广图） |
| 适用场景 | 找到任意路径、回溯问题 | 找到最短路径、层次遍历 |
实现方式
DFS可以通过递归或非递归（使用栈）两种方式实现。以下是递归方式的伪代码示例：
```python
def dfs(node):
if node is visited:
return
mark node as visited
for each neighbor of node:
dfs(neighbor)
```
总结
DFS是一种简单但强大的遍历算法，适用于多种数据结构和问题类型。理解其原理和应用场景有助于在实际编程中灵活运用。虽然DFS可能会陷入无限循环，但通过合理的访问标记机制可以有效避免这一问题。结合不同的数据结构，DFS能够发挥出极大的价值。
