DFS 深度优先搜索：从原理到实战

在算法世界中，深度优先搜索（Depth-First Search，简称 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>>nums[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 的思想与应用场景，在面试与竞赛中灵活应对。