彻底搞懂dfs与回溯

深度优先搜索dfs，其过程是对每一个可能的分支路径深入到不能再深入为止，是一种广泛用于树和图中搜索路径，和其他情况下搜索需要的情况的算法。

lxrrrrrrrr

4296人浏览 · 2022-11-12 00:15:11

lxrrrrrrrr · 2022-11-12 00:15:11 发布

初识dfs

扩展到图

深度优先搜索dfs，其过程是对每一个可能的分支路径深入到不能再深入为止，是一种广泛用于树和图中搜索路径，和其他情况下搜索需要的情况的算法

初识dfs

彻底弄懂dfs和回溯，我们先不讲图，先来个简单的

假如我们要把（1，2，3）这个集合所有的子集都搜索出来

也就是下面这个dfs（n等于3）

也就是下面这个代码

#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int> > res;
vector<int> temp;
int tmp;
void dfs(int idx){
    if(idx==n+1){
        res.push_back(temp);
        for(auto t:temp) cout<<t<<" ";
        cout<<endl;
        return ;
    }

    temp.push_back(idx);
    dfs(idx+1);
    temp.pop_back();
    dfs(idx+1);
}
signed main(){
    cin>>n;
    dfs(1);
}

首先为什么子集能dfs出来呢，对于每一个数，都有要和不要两种答案

他们会产生两个不同的分支，进入下一层，而下一个数又有两种答案.....

比如不要1，要2，不要3，得到的子集就是（2），都不要得到的就是空集

我们画一颗搜索树便于我们理解

一开始我们什么都没有，然后每一层都是要和不要，得到最后的所有答案

那么怎么用代码实现这东西呢

首先idx代表层，最开始等于1，每一层+1，当等于n+1时，说明已经全部走完了，此时temp中就是我们要的答案，这个很好理解

然后对于每一个idx，要这个数就是temp.push_back(idx)，把这个数加进temp中，否则不要他直接dfs下一层，这里我们要回溯了，要把idx这个数pop掉，此时temp中没有这个数，才代表我们不要，然后dfs下一层

通俗的解释下回溯

回溯这个东西就是，假设你现在正处在上图的过程，有一个中间变量 $tmp$ 的值为 $X1$ ,这个中间变量可以是随便一个什么，int或string或数组或其他，而你通过过程去搜索可能1的时候，会改变这个中间变量 $tmp$ ，假设你把他加上了 $d$ ，现在中间变量 $tmp$ 的值为 $tmp+d$

而等你搜完可能1的时候，再去搜索可能2，可能2是要通过过程来的，也就是搜可能2的时候要求 $tmp$ 的值为 $X1$ ，但搜完可能1的时候，这个 $tmp$ 的值为 $X1+d$ ，所以在写代码的时候就要在 dfs可能1 的后面写上 $tmp$ 要减去 $d$ ，这样才能回复过程时的中间变量，才能继续搜索可能2，这就是回溯

简单来说，回溯就是要消除搜索过程中的不同可能性之间对中间变量的影响

我不知道我说明白没有，大家看下图详细过程

如果听懂了

接下来试一个稍微深一点的例子

求长度为n，每个数字可以在1-m中选且不能重复的所有情况

就比如要求长为2，m等于3的所有情况

答案是（1 2）（1 3）（2 1）（2 3）（3 1）（3 2）

看看能不能理解这里的回溯

代码：

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> temp;
int st[100];
void dfs(int idx){
    if(idx==n+1){
        for(auto t:temp) cout<<t<<" ";
        cout<<endl;
        return ;
    }
    for(int i=1;i<=m;++i){
        if(st[i]==0){
            temp.push_back(i);
            st[i]=1;
            dfs(idx+1);
            st[i]=0;//回溯
            temp.pop_back();//回溯
        }
    }
}
signed main(){
    cin>>n>>m;
    dfs(1);
}

这里st代表标记每个数用没用过，很明显，一种可能和另一种可能的st是不能互相干扰的

所以要消除每种可能之间的影响

扩展到图

其实这就不难理解了

树本身就相当于一颗搜索树

而对于图，如果记录下每个点只遍历一次，就也变成了一颗搜索树

假设我们用dfs遍历这张图

#include <bits/stdc++.h>
using namespace std;
vector<int> v[100];
int n,m;
int st[100];
void dfs(int now){
    cout<<"遍历到 "<<now<<endl;
    for(auto t:v[now]){
        if(!st[t]){
            st[t]=1;
            dfs(t);
        }
    }
}
signed main(){
    cin>>n>>m;
    while(m--){
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    st[1]=1;
    dfs(1);
}