一文吃透 DFS 深度优先搜索：从原理到实战

在算法世界中，深度优先搜索（Depth-First Search，简称 DFS）是一种基础且核心的遍历与搜索算法。它以 “纵向挖掘” 为核心思想，沿着一条路径探索至终点后，回溯至前一节点继续探索其他路径，如同迷宫中沿着一条通道走到头，再折返寻找新通道。这种特性让 DFS 在图论遍历、迷宫求解、组合问题、拓扑排序等场景中广泛应用，也是面试与算法竞赛的高频考点。本文将从原理、实现、优化到实战，带你全面掌握 DFS。

一、DFS 核心原理：纵向探索与回溯

1. 核心思想

DFS 的本质是 “不撞南墙不回头”：从起始节点出发，优先探索当前节点的某一条邻接路径，直至无法继续前进（到达终点或已访问节点），再回溯到上一个未探索完所有邻接节点的节点，重复此过程，直至遍历所有可达节点。

2. 关键概念

• 访问标记：为避免重复访问节点（陷入死循环），需用数组或哈希表记录节点是否已被访问。
• 回溯：探索完一条路径后，撤销当前节点的访问标记（若需多次遍历），回到上一节点继续探索其他路径，是 DFS 区别于其他遍历算法的核心。
• 递归与栈：DFS 可通过递归实现（利用函数调用栈隐式维护遍历路径），也可通过显式栈手动实现，两种方式本质一致。

3. 遍历流程示意图

以无向图 1-2-3-4，1-5 为例，DFS 遍历流程（起始节点为 1）：

1. 访问节点 1，标记为已访问；
2. 选择邻接节点 2，访问并标记；
3. 选择节点 2 的邻接节点 3，访问并标记；
4. 选择节点 3 的邻接节点 4，访问并标记；
5. 节点 4 无未访问邻接节点，回溯至 3；
6. 节点 3 无其他未访问邻接节点，回溯至 2；
7. 节点 2 无其他未访问邻接节点，回溯至 1；
8. 选择节点 1 的邻接节点 5，访问并标记；
9. 节点 5 无未访问邻接节点，回溯至 1；
10. 所有节点遍历完成，流程结束。最终遍历顺序：1→2→3→4→5（路径不唯一，取决于邻接节点的遍历顺序）。

二、DFS基础框架（伪代码）

1. 递归实现（简洁直观）

递归是 DFS 最常用的实现方式，利用函数调用栈自动维护回溯路径，代码简洁易懂，适合大部分场景。

伪代码框架

bool visited[]; void dfs(当前节点 u) { visited[u] = true; 处理当前节点 u； 遍历 u 的所有邻接节点 v： 若 v 未访问，则递归调用 dfs(v)； 可选：visited[u] = false； }

2. 栈实现（显式维护路径）

当递归深度过大时（如节点数超过 1e4），会导致栈溢出，此时需用显式栈手动实现 DFS，避免递归栈溢出问题。

伪代码框架

void dfs(起始节点 u) { 初始化栈，将 u 入栈，并标记为已访问； while 栈不为空： 弹出栈顶节点 curr； 处理 curr 节点； 遍历 curr 的所有邻接节点 v： 若 v 未访问，则标记为已访问，入栈； }

三、DFS 基础例题

例题 1：二叉树的最大深度

题目描述：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

题目图片：

题目思路：采用递归式 DFS 遍历二叉树，核心逻辑为：当前节点的最大深度 = 1（当前节点） + 左子树 / 右子树的最大深度（取较大值）；递归终止条件为节点为空（深度为 0）。通过递归遍历左右子树，自底向上计算每个节点的深度，最终得到根节点的最大深度。

AC code

#include<bits/stdc++.h> using namespace std; const int MAX_NODE = 1005; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x):val(x),left(NULL),right(NULL){} }; TreeNode* nodes[MAX_NODE]; int node_cnt=0; TreeNode* build(int val) { nodes[node_cnt++]=new TreeNode(val); return nodes[node_cnt-1]; } int maxDepth(TreeNode* root) { if (root==NULL) return 0; return 1+max(maxDepth(root->left),maxDepth(root->right)); } int main() { TreeNode* root=build(3); root->left=build(9); root->right=build(20); root->right->left=build(15); root->right->right=build(7); cout<<maxDepth(root)<<endl; return 0; }

例题 2：子集

题目描述：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

题目思路:通过 DFS 回溯生成所有子集，核心逻辑为：递归过程中，每一步先将当前路径（已选元素）加入结果集，再遍历剩余元素，选择一个元素加入路径后递归，递归返回后撤销选择（回溯），确保遍历所有组合。用 start 控制遍历起点，避免生成重复子集（如 [1,2] 和 [2,1] 视为同一子集）。

AC code

#include<bits/stdc++.h> using namespace std; const int MAX_N=105; const int MAX_PATH=105; const int MAX_RES=1024; int nums[MAX_N]; int path[MAX_PATH]; int res[MAX_RES][MAX_PATH]; int res_size=0; int path_size=0; int n; void dfs(int start) { for(int i=0;i<path_size;++i) res[res_size][i]=path[i]; res_size++; for(int i=start;i<n;++i) { path[path_size++]=nums[i]; dfs(i+1); path_size--; } } int main() { cin>>n; for(int i=0;i<n;i++) cin>>a[i]; dfs(0); for(int i=0;i<res_size;++i){ for(int j=0;res[i][j]!=0;++j) { cout<<res[i][j]<<" "; } cout<<endl; } return 0; }

例题 3：电话号码的字母组合

题目描述：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

题目图片：

解题思路：用数组存储数字到字母的映射，通过 DFS 回溯生成所有组合：递归参数 index 表示当前处理的数字位置，每一步遍历当前数字对应的所有字母，将字母加入路径后递归处理下一个数字，递归终止条件为处理完所有数字（将当前路径加入结果集），递归返回后撤销字母选择（回溯），遍历所有可能的字母组合。

AC code

#include<bits/stdc++.h> using namespace std; const int MAX_RES=1024; const int MAX_STR=20; char res[MAX_RES][MAX_STR]; int res_size=0; char path[MAX_STR]; int path_len=0; char digits[MAX_STR]; char mapping[10][5]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; void dfs(int index) { if (index==strlen(digits)){ path[path_len]='\0'; strcpy(res[res_size++],path); return; } int num=digits[index]-'0'; for (int i=0;mapping[num][i]!='\0';++i){ path[path_len++]=mapping[num][i]; dfs(index+1); path_len--; } } int main() { cin>>digits; dfs(0); for (int i=0;i<res_size;++i){ cout<<res[i]<<endl; } return 0; }

例题 4：8 皇后

题目描述：

8 皇后问题研究的是如何将 8 个皇后放置在 8×8 的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数 8，返回所有不同的 8 皇后问题的解决方案。每一种解法包含一个明确的 8 皇后问题的棋子放置方案，该方案中 '1' 和 '0' 分别代表了皇后和空位。

#include<bits/stdc++.h> using namespace std; int a[9]; bool b[9],c[17],d[17]; int ans; void print(){ ans++; cout<<"No. "<<ans<<endl; for(int i=1;i<=8;i++){ for(int j=1;j<=8;j++){ if(a[j]==i) cout<<1<<' '; else cout<<0<<' '; } cout<<endl; } } int Dfs(int i){ if(i==9){print(); return 0;} for(int j=1;j<=8;j++){ if(!b[j]&&!c[i-j+7]&&!d[i+j]){ b[j]=1; //占领列 c[i-j+7]=1;//占领两条对角线 d[i+j]=1; a[i]=j;//把皇后的位置存放到a数组里。 Dfs(i+1);//搜索下一行 b[j]=0; //回溯，还原现场 c[i-j+7]=0; d[i+j]=0; } } } int main() { Dfs(1);//从第一行开始放置第一个皇后 }

四、DFS 常见误区与注意事项

1. 忘记标记访问状态：导致节点重复访问，陷入死循环，最终超时或栈溢出。
2. 回溯时未撤销状态：如组合问题中未弹出当前元素，导致组合错误。
3. 递归深度过大：对于深度超过 1e4 的场景（如长链图），递归实现会栈溢出，需改用栈实现。
4. 未剪枝导致效率低下：在组合、排列等问题中，未剪枝会导致时间复杂度爆炸，无法通过大数据测试。

五、总结

DFS 是一种 “纵向探索 + 回溯” 的搜索算法，核心在于 “不撞南墙不回头”，通过递归或栈实现，配合剪枝优化可大幅提升效率。它不仅是图论遍历的基础，更在组合问题、迷宫求解、拓扑排序等场景中发挥着重要作用，是算法学习中必须掌握的核心知识点。

掌握 DFS 的关键在于：理解回溯的本质、熟练运用访问标记、学会针对性剪枝。多做实战题目，才能真正吃透 DFS 的思想与应用场景，在面试与竞赛中灵活应对。