核心考点梳理#

深度优先搜索（DFS）是408数据结构模块中图遍历的核心考点之一，同时也可应用于树的遍历、连通分量求解、拓扑排序、迷宫路径查找等场景，常见考察形式包括代码默写、时间复杂度计算、场景应用分析：

1. 递归版DFS实现原理 递归实现基于程序运行时的系统调用栈，每次访问一个节点后，会递归遍历其所有未被访问的邻接点，直到所有可达节点都被访问完毕。标准邻接表存储下的递归代码框架如下：

   1
   // 假设MAXVEX为最大顶点数，Graph为邻接表存储的图结构体
   2
   bool visited[MAXVEX]; // 全局访问标记数组
   3
   void DFS(Graph G, int v) {
   4
       // 访问当前顶点v
   5
       printf("%d ", G.vertices[v].data);
   6
       visited[v] = true;
   7
       // 遍历v的所有邻接点w
   8
       for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
   9
           if (!visited[w]) {
   10
               DFS(G, w); // 递归访问未被访问的邻接点
   11
           }
   12
       }
   13
   }

2. 非递归版DFS实现思路 手动模拟系统栈的工作流程：将起始顶点压入栈并标记访问，循环弹出栈顶顶点并访问，再将其所有未被访问的邻接点按逆序压入栈（保证与递归遍历顺序一致），直到栈为空。
3. 时间复杂度分析
   • 邻接表存储：每个顶点和边都被访问一次，时间复杂度为 $O(V+E)$，其中$V$为顶点数，$E$为边数
   • 邻接矩阵存储：需要遍历每个顶点的所有邻接矩阵元素，时间复杂度为 $O(V^2)$
4. 常见考察变式 408真题常结合无向图连通分量求解、有向图环检测、拓扑排序等场景考察DFS的应用，同时会对比DFS与BFS的空间、时间复杂度差异。