$DFS$ 就是深度优先搜索。

它是一条路走到不可以（或不可能）成为最优解时再回溯的算法。时间复杂度较 $BFS$ 更大。

例题：洛谷P1706

代码：

#include <bits/stdc++.h>
using namespace std;
int a[10],b[10]={0},n;
void dfs(int x){
    if(x==n+1){
        for(int i=1;i<=n;i++){
            printf("%5d",a[i]);
        }
        printf("%s","\n");
    }
    for(int i=1;i<=n;i++){
        if(b[i]==0){
            b[i]=1;
            a[x]=i;
            check(x+1);
            b[i]=0;
        }
    }
}
int main(){
    scanf("%d",&n);
    dfs(1);
    return 0;
}

例题：洛谷P1460

代码：

#include <bits/stdc++.h>
using namespace std;
int  V,ndv[26],G,vrv[16][26],C[16],LC[16],P=26,nvt[26]={0};//ndv=need vitamin;   vrv=every vitamin;   C=choose;    nvt=now vitamin;   LC=last choose;
bool check(int p){//p为P的一种可能值； 
    for(int i=1;i<=V;i++){
        if(nvt[i]<ndv[i]) return false;
    }
    return true;
}
void dfs(int num,int s){//num为当前选择的饲料编号，s为已选饲料种数； 
    if(num==G+1){
        if(check(s)){
            P=s;
            for(int i=1;i<=P;i++){
                LC[i]=C[i];
            }
        }
    }
    else{
        if(s<P-1){
            for(int i=1;i<=V;i++){
                nvt[i]+=vrv[num][i];
            }
            C[s+1]=num;
            dfs(num+1,s+1);
            for(int i=1;i<=V;i++){
                nvt[i]-=vrv[num][i];
            }
        }
        if(s<P){
            dfs(num+1,s);
        }
    }
}
int main(){
    scanf("%d",&V);
    for(int i=1;i<=V;i++){
        scanf("%d",&ndv[i]);
    }
    scanf("%d",&G);
    for(int i=1;i<=G;i++){
        for(int j=1;j<=V;j++){
            scanf("%d",&vrv[i][j]);
        }
    }
    dfs(1,0);
    cout<<P<<" ";
    for(int i=1;i<=P;i++){
        cout<<LC[i]<<" ";
    }
    return 0;
}

例题：洛谷P1123

代码：

#include<bits/stdc++.h>
using namespace std;
int t,m,n;
int ans,maxn;
int dis[7][7]={0};
int p[7][7];
int tx[9]={0,-1,-1,-1,0,1,1,1,0},ty[9]={0,-1,0,1,1,1,0,-1,-1};
void dfs(int x,int y){
	if(y==m+1){
		dfs(x+1,1);
	}
	else if(x==n+1){
		maxn=max(maxn,ans);
	}
	else{
		dfs(x,y+1);
		if(dis[x][y]==0){
			ans+=p[x][y];
			for(int i=1;i<=8;i++) dis[x+tx[i]][y+ty[i]]++;
			dfs(x,y+1);
			for(int i=1;i<=8;i++) dis[x+tx[i]][y+ty[i]]--;
			ans-=p[x][y];
		}
	}
}
int main(){
	cin>>t;
	while(t--){
		maxn=0;
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++) cin>>p[i][j];
		}
		dfs(1,1);
		cout<<maxn<<endl;
	}
	return 0;
} 

例题：洛谷P2196

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int ans;
vector<int> vc[21],rans;
int a[21];
bool b[21][21],vis[21];
int dfs(int k){
	vc[k].clear();
	vc[k].push_back(k);
	vis[k]=true;
	int m=0;
	for(int i=1;i<=n;i++){
		if(!vis[i]&&b[k][i]){
			int l=dfs(i);
			if(m<l){
				m=l;
				vc[k].clear();
				vc[k].push_back(k);
				for(int j=1;j<=vc[i].size();j++) vc[k].push_back(vc[i][j-1]);
			}
		}
	}
	vis[k]=false;
	m+=a[k];
	return m;
}
int main(){
	cin>>n; 
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			cin>>b[i][j];
		} 
	}
	for(int i=1;i<=n;i++){
		int k=dfs(i);
		//if(i==3) cout<<k<<endl;
		if(ans<k){
			ans=k;
			rans.clear();
			rans=vc[i];
		}
	}
	for(int i=1;i<=rans.size();i++) cout<<rans[i-1]<<" ";
	cout<<endl<<ans;
	return 0;
}

更多题目