DFS（深度优先搜索）
Depth-First Search，深度优先搜索，是图遍历的两种基本方式之一。
核心思想
沿着一条路径尽可能深地探索，直到无法继续（到达叶子节点或遇到已访问节点），然后回溯到上一个分叉点，继续探索其他路径。
类比：走迷宫时，沿着一条路走到头，碰壁后返回最近的岔路口换条路。
代码框架
// 图的 DFS 遍历框架
void traverse(Graph graph, int s, boolean[] visited) {
// base case
if (s < 0 || s >= graph.size()) {
return;
}
if (visited[s]) {
// 防止死循环（处理图中的环）
return;
}
// 前序位置
visited[s] = true;
System.out.println("visit " + s);
for (Edge e : graph.neighbors(s)) {
traverse(graph, e.to, visited);
}
// 后序位置
}
关键特性
| 特性 | 说明 |
|---|---|
| 数据结构 | 递归调用栈（隐式栈）或显式栈 |
| 遍历顺序 | 深度优先，先到底再回溯 |
| visited 数组 | 前序位置标记，防止重复访问和死循环 |
| 适用场景 | 穷举所有路径、拓扑排序、连通分量、环检测 |
与树遍历的关系
图的 DFS 本质上是N叉树遍历基础的延伸：
- 树遍历不需要
visited数组（树无环） - 图遍历必须加
visited数组（图可能有环）
二叉树遍历与 DFS 的关系
DFS 算法属于遍历思路，关注点在单个「节点」：
- 前序遍历：进入节点时做处理（类似 DFS 做选择）
- 后序遍历：离开节点时做处理（类似 DFS 撤销选择）
参见：二叉树系列算法核心纲领
时间复杂度
$O(E + V)$，其中：
- $E$ = 边的总数
- $V$ = 节点的总数