【数据结构DFS】深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着树的深度方向尽可能深入地访问每个分支，直到无法继续为止，然后回溯到上一个节点，继续探索其他未访问的分支。
DFS在许多实际应用中非常有用，如迷宫求解、拓扑排序、连通性判断等。它是递归实现的经典算法之一，也可以使用栈来模拟递归过程。
一、DFS基本原理
| 项目 | 内容 |
| 定义 | 深度优先搜索是一种按深度优先的方式遍历图或树的算法 |
| 实现方式 | 递归或显式栈 |
| 访问顺序 | 先访问当前节点，再依次访问其子节点 |
| 适用场景 | 图的遍历、路径查找、连通性分析、生成树等 |
二、DFS与BFS对比
| 特性 | DFS | BFS |
| 遍历顺序 | 深度优先 | 广度优先 |
| 数据结构 | 栈（递归） | 队列 |
| 空间复杂度 | O(h)，h为树高 | O(n) |
| 适合场景 | 寻找路径、连通性 | 最短路径、层次遍历 |
| 是否能找到最短路径 | 不一定 | 是 |
三、DFS实现步骤
1. 初始化：选择一个起始节点，并标记为已访问。
2. 访问当前节点：处理当前节点的数据。
3. 递归访问邻接节点：对当前节点的所有未访问过的邻接节点进行DFS。
4. 回溯：当所有邻接节点都被访问后，返回上一层递归。
四、DFS应用场景
| 应用场景 | 说明 |
| 迷宫求解 | 找出从起点到终点的路径 |
| 连通分量检测 | 判断图中各部分是否相连 |
| 拓扑排序 | 在有向无环图中确定任务执行顺序 |
| 生成树 | 构建图的生成树结构 |
| 解决数独 | 通过尝试不同可能性寻找可行解 |
五、DFS优缺点
| 优点 | 缺点 |
| 简单易实现 | 可能会陷入无限循环（如存在环） |
| 占用内存较少（相对于BFS） | 不一定能找到最优解 |
| 适用于树和图的遍历 | 对于大图可能效率较低 |
六、DFS代码示例（Python）
```python
def dfs(graph, start, visited):
if start not in visited:
print(start)
visited.add(start)
for neighbor in graph[start]:
dfs(graph, neighbor, visited)
示例图
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C'
}
visited = set()
dfs(graph, 'A', visited)
```
总结
DFS是一种基于深度优先的遍历算法，适用于多种图结构的处理。它在实现上较为简单，但在某些情况下可能不如广度优先搜索高效。合理选择遍历方式是解决问题的关键。
