深搜回溯与不回溯的区别

雨点打透心脏的1/2处 2023-07-03 07:17 16阅读 0赞

一、需要不断尝试以达到最终目的时需要回溯，比如数独、全排列。

以下为全排列代码：

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    string str;
    string temp;
    vector<bool> vis;
    void dfs(int cnt,int n)
    {
        if(cnt==n)
        {
            cout<<temp<<endl;
            return;
        }
        for(int i=0;i<n;i++)
        {
            if(vis[i]==false)
            {
                temp.push_back(str[i]);
                vis[i]=true;
                dfs(cnt+1,n);
                vis[i]=false;
                temp.pop_back();
            }
        }
    }
    int main()
    {
        getline(cin,str);
        sort(str.begin(),str.end());
        int n=str.size();
        vis.resize(n);
        dfs(0,n);
        return 0;
    }

搜完了回来了需要重置vis状态。

二、一锤子买卖时不需要回溯，比如图的深度优先遍历、二叉树节点间的最大距离问题。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3Njg4MQ_size_16_color_FFFFFF_t_70][]

#include <cstdio>
    #include <vector>
    #include <cstring>
    using namespace std;
    struct node
    {
        int up;
        int left;
        int right;
    };
    node tree[500001];
    bool vis[500001];
    int n;
    int root;
    int maxcnt=-1;
    int stroot=0;
    void dfs(int root,int cnt)
    {
        vis[root]=true;
        if(cnt>maxcnt)
        {
            stroot=root;
            maxcnt=cnt;
        }
        //printf("root=%d cnt=%d maxcnt=%d\n",root,cnt,maxcnt);
        if(root==0)
        {
            return;
        }
        if(vis[tree[root].up]==false)
        {
            dfs(tree[root].up,cnt+1);
        }
        if(vis[tree[root].left]==false)
        {
            dfs(tree[root].left,cnt+1);
        }
        if(vis[tree[root].right]==false)
        {
            dfs(tree[root].right,cnt+1);
        }
    }
    int main()
    {
        scanf("%d%d",&n,&root);
        int i;
        for(i=1;i<=n;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            tree[a].left=b;
            tree[a].right=c;
            tree[b].up=a;
            tree[c].up=a;
        }
        memset(vis,0,sizeof(vis));
        dfs(root,0);
        memset(vis,0,sizeof(vis));
        dfs(stroot,0);
        printf("%d\n",maxcnt+1);
        return 0;
    }

**欢迎大家关注/订阅我的微信公众号Code Art Online，我会在我的公众号分享个人见闻，发现生活趣味；这里不仅有0和1，还有是诗和远方↓↓↓**

![20200227123106884.jpg][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3Njg4MQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200204102546193.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3Njg4MQ==,size_16,color_FFFFFF,t_70
[20200227123106884.jpg]: https://img-blog.csdnimg.cn/20200227123106884.jpg