什么是深度优先搜索（DFS）？

Question

什么是深度优先搜索（DFS）？

Accepted Answer

**DFS** 通过沿着每个分支尽可能深入来探索图，然后回溯。它使用**栈**（通常通过递归使用调用栈），在探索替代方案之前访问完整的路径。

## 思想

从一个节点开始，递归进入一个未访问的邻接节点，并不断深入；当无法继续时，回退并尝试另一个分支。

## 示例

```python
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    order = [node]
    for nbr in graph[node]:
        if nbr not in visited:
            order += dfs(graph, nbr, visited)  # go deeper first
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
dfs(graph, 'A')                        # -> ['A', 'B', 'D', 'C']
```

## BFS vs DFS

| | BFS | DFS |
|---|-----|-----|
| 数据结构 | queue | stack / recursion |
| 找到的路径 | 最短（无权重） | 任何路径 |
| 内存 | O(V) 前沿 | O(depth) |
| 适用于 | 最短路径、层级 | 环检测、拓扑排序、连通分量 |

## 复杂度

- **时间：** O(V + E)。**空间：** O(V)（递归深度 + 已访问）。

## 陷阱

深度过大的图可能导致递归栈溢出——使用显式栈。追踪 `visited` 来处理环。

## 为什么这很重要

DFS 是环检测、拓扑排序、连通分量和迷宫/路径生成的基础。

它的递归优雅性使树和图的代码简洁。

了解何时深度优先搜索优于广度优先搜索是图算法流畅性的核心。

	BFS	DFS
数据结构	queue	stack / recursion
找到的路径	最短（无权重）	任何路径
内存	O(V) 前沿	O(depth)
适用于	最短路径、层级	环检测、拓扑排序、连通分量