深度优先搜索框架

^-^

2026-07-20 11:08:19

发布于：四川

32阅读

0回复

0点赞

C++ 框架目录

求赞和评论
以下仅供参考
~~小广告~~ 我发现了一个好玩的深度优先搜索的动画可以辅助你理解
要用记得按题意修改

深度优先搜索

排列

#include <bits/stdc++.h>
using namespace std;
int vis[15];
int a[15];
int n;

void dfs(int x){
    if(x==n+1){
        for(int i=1;i<=n;i++) cout<<a[i]<<" ";
        cout<<"\n";
        return ;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=1;
            a[x]=i;
            dfs(x+1);
            vis[i]=0;
        }
    }
}
int main(){
     cin>>n;
    dfs(1);
    
    return 0;
}

组合

#include <bits/stdc++.h>
using namespace std;
int vis[105];int a[105];
int n;

void dfs(int x){
    if(x==n+1){
        for(int i=1;i<=n;i++) cout<<a[i]<<" ";
        cout<<"\n";
        return ;
    }
    for(int i=a[x-1]+1;i<=n;i++){
        
        a[x]=i;
        dfs(x+1);
          
    }
}
int main(){
    cin>>n;
    dfs(1);
    
    return 0;
}

*迷宫

#include <bits/stdc++.h>
using namespace std;
int run[][2]={1,0,0,1,0,-1,-1,0};
int vis[45][45];
int n,m;
bool f;
bool pa(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=m;
}
void dfs(int x,int y){
    if(f) return;
    if(x==n&&y==m){
        f=1;
        return ;
    }
    for(int i=0;i<=3;i++){
        int ty=y+run[i][1],tx=x+run[i][0];
        
        if(pa(tx,ty)&&!vis[tx][ty]){
            vis[tx][ty]=1;
            
            dfs(tx,ty);
            vis[tx][ty]=0;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;
            cin>>c;
            if(c=='#') vis[i][j]=0; //#是输入的墙
            else vis[i][j]=1;
        }
    }
    vis[1][1]=1;
    dfs(1,1);
    if(f) cout<<"YES";//找到了输出YES否则输出NO
    else cout<<"NO";//其他的题，只用按题意修改即可
    return 0;
}

图论深度优先搜索
题目：朋友圈

#include <bits/stdc++.h>
using namespace std;
int vis[100005];
int n,m;

vector<int> ve[200005];
void dfs(int x){
    vis[x]=1;
    for(int i=0;i<ve[x].size();i++){
        int y=ve[x][i];
        if(!vis[y]){
            dfs(y);
        }
    }
}
int main(){
    cin>>n>>m;
    int u,v;
    for(int i=1;i<=m;i++){
    	
        cin>>u>>v;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dfs(i);
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

佛祖保佑：

/*
 *                    _ooOoo_
 *                   o8888888o
 *                   88" . "88
 *                   (| -_- |)
 *                    O\ = /O
 *                ____/`---'\____
 *              .   ' \\| |// `.
 *               / \\||| : |||// \
 *             / _||||| -:- |||||- \
 *               | | \\\ - /// | |
 *             | \_| ''\---/'' | |
 *              \ .-\__ `-` ___/-. /
 *           ___`. .' /--.--\ `. . __
 *        ."" '< `.___\_<|>_/___.' >'"".
 *       | | : `- \`.;`\ _ /`;.`/ - ` : | |
 *         \ \ `-. \_ __\ /__ _/ .-` / /
 * ======`-.____`-.___\_____/___.-`____.-'======
 *                    `=---='
 *
 * .............................................
 *          佛祖保佑             永无BUG
 */

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论