递归——深度优先搜索(dfs)

递归——深度优先搜索(dfs)

区别与广度优先(bfs)，深度优先注重的是一步走到底，通俗的举一个例子，比如一个迷宫，每走一格他就有很多的方向可以走，而深度优先就是先选取一个方向并且一路走到底直到触边或无路可走时再返回。以下使用递归方法实现深度优先搜索：

递归方法类似于栈，将数据一直递取到底后自下往上出栈。

大致框架如下：

viod dfs(int k){
    if(输出条件){
        cout<<
    }
    else{
        for(int i=0;i<n;i++){
            if(vis[i]==0){
                a[k]=数字,vis[i]=1//标记使用;
                dfs(k+1);//向下递取
                vis[i]=0;//将其拿出，返回原先状态
            }
        }
    }
}

下列题目方式解决一些排列组合问题。

组合输出 –5个数字组合输入3个盒子

#include<bits/stdc++.h>
using namespace std;
int m,n,r;
int a[200],vis[200];//a用来记录牌子，vis用来记录牌子的使用情况

int is_rise(int b[]){//判断是否是递增数组
    int flag=1;
    for(int i=1;i<r;i++){
        if(a[i]>a[i+1]){
            flag=0;
        }
    }
    return flag;
}

void dfs(int k){//k为盒子的编号，或可以理解为步数
    if(k==r+1&&is_rise(a)){
        for(int i=1;i<=r;i++){
            cout<<a[i]<<" ";
        }
        cout<<"\n";
        return;
    }
    for(int i=1;i<=n;i++){//注意只要一个for来表示其手上所拿的牌即可，不要用两个for，递归里面就包含了向下循环的方式，就是一遍一遍尝试放牌。
        if(vis[i]==0){
            a[k]=i,vis[i]=1;
            dfs(k+1);
            vis[i]=0;//将牌子拿出来，此时就要把vis归回0
        }
    }
}
int main(){
    cin>>n>>r;
    dfs(1);
}

这题不用暴力for循环做解，而是考虑用三个盒子装入数字，装入过的数字用1标记箱子被使用。

素数环

eg：输入8 输出4

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

int isPrime(int x){
    if(x<2)return 0;
    for(int i=2;i*i<=x;i++){
        if(x%i==0)return 0;
    }
    return 1;
}

void dfs(int k){
    if(k==n+1 && isPrime(a[1]+a[n])){//是否超出边界&&是否头尾相加是素数
        cnt++;
        return;
    }
    for(int i=2;i<=n;i++){
        if(vis[i]==0 && isPrime(i+a[k-1])){//vis用来看有没有用过这个数字
            a[k]=i,vis[i]=1;//a用来保存数字
            dfs(k+1);
            vis[i]=0;//当前的这个数字清除，再向下dfs
        }
    }
}
int main(){
    cin>>n;
    a[1]=1,vis[1]=1;
    dfs(2);
    cout<<cnt; 
}

全排列问题

#include <bits/stdc++.h>
using namespace std;
int n;
int a[25],b[25]; //a用来存储数字，到时候输出就看a里面存的数字；b用来记录数字使用过没有，如果用了就用1表示，没用就是0；比如1 2 3，在存放第二个盒子的时候1已经用过了，故用b[i]==0来判断出可以用2，再把2放到盒子里
void dfs(int k){ //depth first search
	if(k==n+1){ //k是指到第几个盒子了，如果k到了第n+1个虚无的盒子，就说明没盒子了要输出了
		for(int i=1;i<=n;i++){
			printf("%d ",a[i]);
		}
		printf("\n");
		return;
	}
	for(int i=1;i<=n;i++){//i是指拿在你手上的牌的数字，没用0为了更好理解
		if(b[i]==0){//看看这个牌用过没有，b数组用来看这个牌用过没有用的
			a[k]=i,b[i]=1;//如果没有用过就把牌i放到第k个盒子里，用a[k]=i表示，再用b[i]=1表示这个牌用了
			dfs(k+1);//上一步只放了一张牌，这一步就是看到第二个盒子，在这次i会发现b[1]=1，因此此时i会为2，并把2放到盒子里
			b[i]=0;//就是把当前的这张牌拿出来，比如n=3时，它时在dpf(3)时先将i=3的拿出来，然后再退回上一个dpf(2)把i=2那出来，然后dpf(2)这段又会i+1变成3，此时又到dps(3)里，以此类推		
	}}
}
int main(){
	scanf("%d",&n);
	dfs(1);
}

体积

#include <bits/stdc++.h>
using namespace std;

int n,cnt;
int a[25],vis[1005];

void dfs(int k,int sum){
    if(k==n+1){
//      cout<<sum<<" ";
        vis[sum]=1;
        return;
    }
    dfs(k+1,sum+a[k]);
    dfs(k+1,sum);
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dfs(1,0);
    for(int i=1;i<=1000;i++){
        if(vis[i])cnt++;
    }
    cout<<cnt;
    return 0;
}

若把上面代码的注释删除则可以得到：

3
1 3 4
8 4 5 1 7 3 4 0 6

由此可知上面深度搜索遍历的顺序是：

1+3+4
1+3
1+4
1
3+4
3
4
0

以上手写笔记逐个分析dfs递归情况，方便理解两个dfs同时出现的状态。

相当于第一个dfs一个一个出栈，出栈一个数据就进入下一个栈再进行递取。