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

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

题目图片：

题目思路：采用递归式 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 的思想与应用场景，在面试与竞赛中灵活应对。