深度优先搜索 (DFS) 算法原理与 C++ 实现

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 具体步骤：

1. 访问 A，标记已访问。
2. 从 A 的第一个邻接点 B 出发，访问 B，标记。
3. 从 B 的第一个邻接点 C 出发，访问 C，标记。
4. C 无未访问邻接点，回溯到 B。
5. 从 B 的下一个邻接点 D 出发，访问 D，标记。
6. D 无未访问邻接点，回溯到 B；B 也无其他邻接点，回溯到 A。
7. 从 A 的下一个邻接点 E 出发，访问 E，标记。
8. 从 E 的第一个邻接点 F 出发，访问 F，标记。
9. F 无未访问邻接点，回溯到 E；E 无其他邻接点，回溯到 A。
10. A 所有邻接点访问完毕，结束。

1.3 三色标记法

在 DFS 执行过程中，常用三种颜色标记节点状态，这有助于理解递归栈和回溯：

• 白色：尚未发现的节点（未被访问）。
• 灰色：已发现但尚未处理完所有邻接点的节点（当前在递归栈中）。
• 黑色：所有邻接点都已处理完毕的节点（已完成探索）。

这个标记法在环检测、拓扑排序等高级应用中至关重要。

1.4 算法步骤（递归版本）

DFS 通常用递归实现，天然契合'深入 - 回溯'的过程：

void DFS(int u) {
    // 标记 u 为已访问（白色 → 灰色）
    visited[u] = ;
     ( v : adj[u]) {
         (!visited[v]) {
            (v);
        }
    }
    
}