彻底搞懂dfs与回溯

目录

初识dfs 

 扩展到图

---

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

初识dfs 

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

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

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

也就是下面这个代码

#include 
using namespace std;
int n;
vectorint> > res;
vector<int> temp;
int tmp;
void dfs(int idx){
    if(idx==n+1){
        res.push_back(temp);
        for(auto t:temp) cout<" ";
        cout<
        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下一层

通俗的解释下回溯

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

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

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

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

如果听懂了

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

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

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

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

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

代码：

#include 
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<" ";
        cout<
        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 
using namespace std;
vector<int> v[100];
int n,m;
int st[100];
void dfs(int now){
    cout<<"遍历到 "<
    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);
}

输出如下

诶这对比之前那两个是不少了点啥

咋不回溯了呢

之前dfs后面不是得st[t]=0吗

对呀，咋不回溯了呢

大家可以写个回溯试试

 是不是重复遍历了很多点呀

因为遍历图的时候每个点只遍历一遍呀

如果回溯了，我现在这条路遍历到3这个点，之后消除影响了，那我其他另一条路在碰到3这个点是不是还要走一遍呀，那不就重复遍历了吗

这种情况是必须要不同可能之间要产生影响的，并且这个影响不能被消除，回溯不就是消除影响吗，所以不回溯了

如果以上都理解了，那dfs和回溯最底层的逻辑也就差不多这些了

睡觉睡觉..