1. 深度优先搜索 (DFS) 核心原理
1.1 核心思想：一条路走到黑
DFS 的核心思想可以用一句俗语概括：'不撞南墙不回头'。它从起点出发，沿着一条路径尽可能深地探索，直到无法继续（没有未访问的邻接点或到达目标），然后回溯到上一个分支点，选择另一条未走过的路径继续探索，直到遍历完所有可达节点。
形象比喻：你在迷宫中，随便选一个方向，一直往前走，遇到死胡同就退回到上一个岔路口，换一个方向继续走。这个过程就是 DFS。
1.2 工作过程详解
我们通过一个简单的树形结构来可视化 DFS 的工作过程（节点访问顺序用数字标记）：
A(1)
/ \
B(2) E(5)
/ \ \
C(3) D(4) F(6)
从 A 出发的 DFS 遍历顺序为：A → B → C → D → E → F 具体步骤：
- 访问 A，标记已访问。
- 从 A 的第一个邻接点 B 出发，访问 B，标记。
- 从 B 的第一个邻接点 C 出发，访问 C，标记。
- C 无未访问邻接点，回溯到 B。
- 从 B 的下一个邻接点 D 出发，访问 D，标记。
- D 无未访问邻接点，回溯到 B；B 也无其他邻接点，回溯到 A。
- 从 A 的下一个邻接点 E 出发，访问 E，标记。
- 从 E 的第一个邻接点 F 出发，访问 F，标记。
- F 无未访问邻接点，回溯到 E；E 无其他邻接点，回溯到 A。
- A 所有邻接点访问完毕，结束。
1.3 三色标记法
在 DFS 执行过程中，常用三种颜色标记节点状态，这有助于理解递归栈和回溯：
- 白色：尚未发现的节点（未被访问）。
- 灰色：已发现但尚未处理完所有邻接点的节点（当前在递归栈中）。
- 黑色：所有邻接点都已处理完毕的节点（已完成探索）。
这个标记法在环检测、拓扑排序等高级应用中至关重要。
1.4 算法步骤（递归版本）
DFS 通常用递归实现，天然契合'深入 - 回溯'的过程：
void DFS(int u) {
// 标记 u 为已访问（白色 → 灰色）
visited[u] = ;
( v : adj[u]) {
(!visited[v]) {
(v);
}
}
}
