深度优先遍历DFS：从入门到精通

一、先解答上次的思考题

无向图：顶点 0-1-2-3，边：0-1、0-2、1-2、2-3

• 邻接矩阵：对应位置置 1
• 邻接表：每个顶点链表列出邻居

二、今天学习目标

1. 理解DFS 深度优先遍历
2. 记住核心思想：一条路走到黑，走不通再回头
3. 用邻接矩阵 + 递归实现 DFS
4. 完整可运行代码

三、什么是 DFS？

DFS：Depth First Search深度优先，先走到底，再回溯

可以理解为：

• 走迷宫：一直往前，遇到岔路选一条，走不通就退回来换一条
• 树的前序遍历，就是 DFS 的一种

关键点：

• 需要visited 数组标记是否走过
• 一般用递归最简单

四、DFS 基本步骤

1. 访问当前节点，标记visited[u] = 1
2. 遍历所有邻居v
3. 如果v没被访问，递归 DFS (v)

五、完整代码：邻接矩阵 + DFS

#include <stdio.h> #define N 5 // 邻接矩阵 int graph[N][N] = {0}; // 访问标记 int visited[N] = {0}; // 添加无向边 void addEdge(int u, int v) { graph[u][v] = 1; graph[v][u] = 1; } // DFS 核心 void dfs(int u) { // 访问当前节点 printf("%d ", u); visited[u] = 1; // 遍历所有可能邻居 for (int v = 0; v < N; v++) { // 有边且未访问 if (graph[u][v] == 1 && !visited[v]) { dfs(v); } } } int main() { // 构建图 addEdge(0, 1); addEdge(0, 2); addEdge(1, 3); addEdge(1, 4); addEdge(3, 4); printf("DFS 遍历顺序："); dfs(0); return 0; }

六、运行结果示例

DFS 遍历顺序：0 1 3 4 2

（具体顺序可能因邻接矩阵遍历顺序略有不同，均属正确）

七、DFS 适用场景

• 连通性判断
• 迷宫求解
• 寻找路径
• 拓扑排序
• 求连通块数量

八、今日小练习

图：顶点：0 1 2 3边：0-1，0-2，1-2，2-3

从 0 开始 DFS，写出遍历顺序。