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

一、先解答上次的思考题无向图顶点 0-1-2-3边0-1、0-2、1-2、2-3邻接矩阵对应位置置 1邻接表每个顶点链表列出邻居二、今天学习目标理解DFS 深度优先遍历记住核心思想一条路走到黑走不通再回头用邻接矩阵 递归实现 DFS完整可运行代码三、什么是 DFSDFSDepth First Search深度优先先走到底再回溯可以理解为走迷宫一直往前遇到岔路选一条走不通就退回来换一条树的前序遍历就是 DFS 的一种关键点需要visited 数组标记是否走过一般用递归最简单四、DFS 基本步骤访问当前节点标记visited[u] 1遍历所有邻居v如果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-10-21-22-3从 0 开始 DFS写出遍历顺序。