#创作计划#DFS的基础和提高

李睿尧

2025-08-26 11:38:31

发布于：上海

7阅读

0回复

0点赞

基础

DFS，深度优先搜索，是一种在搜索中较为常见的算法。主要用于解决“选和不选”和”选几个“的问题，通过一个choose数组和多次递归操作，解决问题。DFS一般是这样的：

bool choose[200005] = {false};
void check(){
    //用于检查当前遍历的结果是否合法（选择性使用）
}
void dfs(int now){
    if(now == n+1){//n表示需要计算的数组长度
        check();
        return ;
    }
    //分别枚举第now次选和不选两种情况，并继续递归
    choose[now] = true;
    dfs(now+1);
    choose[now] = false;
    dfs(now+1);
}

从上述模板当中可以看出，DFS一般来说需要几个必要变量：

1.一个正整数n，用于表示数组长度。
2.需要计算的数组a。
3.一个数组choose。

此外，在许多题目中，由于并不是每组数据都合法，所以DFS一般来说会与一个check()函数共同出现。check()函数用于检查每一组DFS的结果是否合法。答案一般是一个全局整型变量，也就是一部分题目中的

int ans = 0;

特别地，ans变量一定要开在check函数前面，否则会导致平时所说的”先用后付“———先使用后定义的错误，以至于程序无法正常运行。

那么下面展示一道简单的DFS题目的解法：（题目A140-数字全排列）：

#include <iostream>
using namespace std;
int n,choose[200005],cnt[200005];
void check(){
    for(int i = 1;i <= n;i++)cnt[i] = 0;
    for(int i = 1;i <= n;i++){
        cnt[choose[i]]++;
    }
    for(int i = 1;i <= n;i++){
        if(cnt[i] != 1)return ;//防止没有或者重复
    }
    for(int i = 1;i <= n;i++){
        cout << choose[i] << ' ';
    }
    cout << endl;
}
void dfs(int now){
    if(now == n + 1){//检测是否完成，结束递归
        check();
        return ;
    }
    for(int i = 1;i <= n;i++){//循环遍历每一种情况
        choose[now] = i;
        dfs(now+1);
    }
}
int main(){
    cin >> n;
    dfs(1);//从第一项开始遍历
}

所以，DFS其实可以被理解成是一种进阶的递归，通过多次递归，计算出答案。

提高

DFS算法一般来说只在CSP-J组中考察，由于时间复杂度较高，它在难题中一般用于解决部分分的骗分问题。也就是说，DFS在CSP-S及以上的比赛中，只能被用于暴力代码，进行对拍或者部分分解决。
参加过2025小码王集训营的可以去那个团队的题库里找到一道名叫”众最大数“的题目。这道题目的正解是通过求数组最大值得到的，此处不再展示。这道题就可以通过DFS获得30%的分数,有兴趣的可以自行尝试一下。

好啦，以上就是全部内容，感谢观看！

有帮助，赞一个