DFS实质就是一种枚举，不过借助递归实现；
DFS的基本模式：
void dfs(int step)
{
判断边界；
for（int i=1;i<=n;++i)//尝试每一种可能；
{
dfs(step+1);/‘/继续下一步
}
返回；
}
例题：
问题描述：
现有等式：【】【】【】+【】【】【】=【】【】【】，要求在每一个【】中填入0~9中某一个数字，最后使得等式成立且每个数字使用一次，输出等式，并输出总个数；例如782+154=936，154+782=936只计数一次，但输出时都输出；
基本思路：
对每一个【】进行深搜；
代码如下：
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>



using namespace std;

int a[10],book[10];

int total;

void dfs(int step)

{

    if(step==10)

    {

        if(a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]==a[7]*100+a[8]*10+a[9])

        {

            for(int i=1;i<=9;i++)

            {

                printf("%d",a[i]);

                if(i==3) printf("+");

                else if(i==6) printf("=");

            }

            printf("\n");

            total++;

        }

    }

    for(int i=1;i<=9;i++)//可以体现枚举；

    {

        if(book[i]==0)

        {

            a[step]=i;

            book[i]=1;

            dfs(step+1);//对下一个【】进行深搜；

            book[i]=0;//恢复；

        }

    }

    return;

}

int main()

{

    dfs(1);

    printf("%d\n",total/2);

    return 0;

}

基本概念


深度优先搜索算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。


算法思想

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 



 

基本模板

int check(参数)
{
    if(满足条件)
        return 1;
    return 0;
}

void dfs(int step)
{
        判断边界
        {
            相应操作
        }
        尝试每一种可能
        {
               满足check条件
               标记
               继续下一步dfs(step+1)
               恢复初始状态（回溯的时候要用到）
        }
}   

问题示例

1、全排列问题

//全排列问题
#include<stdio.h>
#include<string.h>

int n;
char  a[15];
char re[15];
int vis[15];
//假设有n个字符要排列，把他们依次放到n个箱子中
//先要检查箱子是否为空，手中还有什么字符，把他们放进并标记。
//放完一次要恢复初始状态，当到n+1个箱子时，一次排列已经结束
void dfs(int step)
{
    int i;
    if(step==n+1)//判断边界
    {
        for(i=1;i<=n;i++)
            printf("%c",re[i]);
        printf("\n");
        return ;
    }
    for(i=1;i<=n;i++)//遍历每一种情况
    {
        if(vis[i]==0)//check满足
        {
            re[step]=a[i];
            vis[i]=1;//标记
            dfs(step+1);//继续搜索
            vis[i]=0;//恢复初始状态
        }
    }
    return ;
}

int main(void)
{
    int T;
    scanf("%d",&T);
    getchar();
    while(T--)
    {
        memset(a,0,sizeof(a));
        memset(vis,0,sizeof(vis));//对存数据的数组分别初始化
        scanf("%s",a+1);
        n=strlen(a+1);
        dfs(1);//从第一个箱子开始
    }
    return 0;
}

2、一个环由个圈组成，把自然数1，2，…，N分别放在每一个圆内，数字的在两个相邻圈之和应该是一个素数。 注意：第一圈数应始终为1。

input: N(0~20)

output:输出格式如下所示的样品。每一行表示在环中的一系列圆号码从1开始顺时针和按逆时针方向。编号的顺序必须满足上述要求。打印解决方案的字典顺序。

//Prime Ring Problem
//与上面的全排列问题其实思路差不多，只是需要判断的条件比较多
//化大为小

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int book[25];
int result[25];
int n;
int num;
//判断是否为素数
int prime(int n)
{
    if(n<=1)
        return 0;
    int i;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
            break;
    }
    if(i*i>n)
        return 1;
    return 0;
}
//判断是否能将当前的数字放到当前的圈内
int check(int i,int step)
{
    if((book[i]==0) && prime(i+result[step-1])==1)
    {
        if(step==n-1)
        {
            if(!prime(i+result[0]))
                return 0;
        }
        return 1;
    }
    return 0;
}

void dfs(int step)
{
    if(step==n)//判断边界
    {
        int a;
        printf("%d",result[0]);
        for(a=1;a<n;a++)
        {
            printf(" %d",result[a]);
        }
        printf("\n");
        return ;
    }
    int i;
    for(i=2;i<=n;i++)//遍历每一种情况
    {
        if(check(i,step))//check是否满足
        {
            book[i]=1;//标记
            result[step]=i;//记录结果
            dfs(step+1);//继续往下搜索
            book[i]=0;//恢复初始状态
        }
    }
}

int main(void)
{

    while(scanf("%d",&n)!=EOF)
    {
        num++;
        memset(result,0,sizeof(result));
        memset(book,0,sizeof(book));
        result[0]=1;
        printf("Case %d:\n",num);//格式比较容易出错
        dfs(1);
        printf("\n");
    }
    return 0;
}


3、油田问题

问题：GeoSurvComp地质调查公司负责探测地下石油储藏。 GeoSurvComp现在在一块矩形区域探测石油，并把这个大区域分成了很多小块。他们通过专业设备，来分析每个小块中是否蕴藏石油。如果这些蕴藏石油的小方格相邻，那么他们被认为是同一油藏的一部分。在这块矩形区域，可能有很多油藏。你的任务是确定有多少不同的油藏。

input: 输入可能有多个矩形区域（即可能有多组测试）。每个矩形区域的起始行包含m和n，表示行和列的数量，

1<=n,m<=100，如果m =0表示输入的结束，接下来是n行，每行m个字符。每个字符对应一个小方格，并且要么是’*’，代表没有油，要么是’@’，表示有油。

output: 对于每一个矩形区域，输出油藏的数量。两个小方格是相邻的，当且仅当他们水平或者垂直或者对角线相邻（即8个方向）。

//A - Oil Deposits 
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

char a[105][105];
int n,m,result;
int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};//表示8个方向

int check(int x,int y)//检查是否有油田
{
    if(x>=0&&x<m&&y>=0&&y<n&&a[x][y]=='@')
        return 1;
    return 0;
}

int dfs(int x, int y)
{
    int i,xx,yy;
    if(check(x,y))
    {
        a[x][y]='.'; //统计之后就可以把该油田标记，且不用恢复（要不会重复），
                    //也可以用一个数组来存每个点的访问情况，但是感觉没必要，浪费空间
        for(i=0;i<8;i++)
        {
            xx=x+dir[i][0];
            yy=y+dir[i][1];
            dfs(xx,yy);//依次检查8个方向
        }
        return 1;
    }
    return 0;
}

int main(void)
{
    int i,j;
    while(scanf("%d %d",&m,&n)==2)
    {
        if(m==0&&n==0)
            break;
        result = 0;
        memset(a,0,sizeof(a));
        for(i=0;i<m;i++)
            scanf("%s",a[i]);
        for(i=0;i<m;i++)//在每一个点都搜索一次
        {
            for(j=0;j<n;j++)
            {
                if(dfs(i,j))//找到油田就可以将结果加1
                    result++;
            }
        }
        printf("%d\n",result);
    }
    return 0;
}

4、棋盘问题

问题：在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

input： 输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

output：对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int n, k, ans;
char str[10][10];
int vis[100];

void dfs(int r, int k)
{
    if(k==0)//判断边界，此时棋子已经放完
    {
        ans++;
        return;
    }

    for(int i=r; i<n; i++)//每次都从放过棋子下一行开始搜索，保证不重复
    {
        for(int j=0; j<n; j++)
        {
            //循环保证行不重复，check保证列不重复
            if(str[i][j]=='.' || vis[j]==1)
                continue;//不满足条件直接跳过
            vis[j] = 1;//标记
            dfs(i+1, k-1);//继续下一次标记
            vis[j] = 0;//恢复初始状态
        }
    }
}

int main(void)
{
    while(1)
    {
        scanf("%d %d", &n, &k);
        getchar();
        if(n==-1 && k==-1) 
            break;
        memset(str, '\0', sizeof(str));
        memset(vis, 0, sizeof(vis));
        ans = 0;

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
                str[i][j] = getchar();
            getchar();
        }

        dfs(0, k);//从第0行开始放，此时手中还剩k个棋子
        printf("%d\n", ans);
    }
    return 0;
}


参考文章

https://blog.csdn.net/ldx19980108/article/details/76324307#commentBox

https://blog.csdn.net/qq_42815188/article/details/89258074

https://www.jianshu.com/p/5cda08b4b391

前言
看了许多的关于dfs的博客，自己也研究了好多遍，最终算是入门了，下面就简单的个人理解的原理以及结合一个简单的全排列实例进行讲解。
原理简介
DFS基于递归思想，递归思想就是把一个事拆分成若干见相同的小事共同组合完成，具体见下图的斐波那契的图文解决



这就是一个最典型的递归，入口f(5)出口就是每次递归的return；

说完递归就是dfs，其有两个重要的标志，也就是两个数组，一个用来标记该点是否被访问过，一个用来把该点放入数组，所以这两个标记是相辅相成的，一定同时出现；dfs就是随机选定一个起点将其标记为已经访问过的点，然后就是递归调用进行与其相邻的点的搜索，直到所有的点都被访问完。

话不多说上例子

全排列，也就是1-n，输出其所有的排列结果。

代码如下，接下来会详细解读代码：
#include <stdio.h>
#include <iostream>
using namespace std;
int a[101],b[101],n;
void print()
{
	int i;
	for(i=1;i<=n;i++)
	{
		cout<<a[i]<<' ';
	}
	cout<<endl;
}
inline void dfs(int i) 
{
	int j;
	if(i==n+1)
	{
		print();
		return;
	}
	for(j=1;j<=n;j++)
	{
		if(b[j]==0)
		{
			a[i]=j;
			b[j]=1;
			dfs(i+1);
			b[j]=0;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	dfs(1);
	return 0;
}


注：以上代码来自csdn博客  Apro1066。

这个代码看上去不多，但是确实经典，有好多值得推敲的东西。

首先主函数中的dfs(1)这是dfs函数进入，传入参数1就是从1开始，主要在dfs函数的理解，下面的图片展示了展示了这个过程。


下面是一个DFS的经典问题-走迷宫,大家可以结合代码做进一步的理解。


Code
#include<bits/stdc++.h>
using namespace std;
bool a[101][101]={0};
char b[101][101];   //存放迷宫 
int flag=0;     //如果能走出去就标记为1，反之为0
int xx[4]={0-1,0,1},yy[4]={-1,0,1,0};
int n,kx,ky;   //n是迷宫的边长，kx是x进行加减之后的值，同理ky。 
void dfs(int x,int y){
	for(int i=0;i<=3;i++){
		kx=x+xx[i];
		ky=y+yy[i];
		if((b[kx][ky] == '.'||b[kx][ky] == 'e')&&kx>=0&&ky>=0&&kx<n&&ky<n&&a[kx][ky]==0){
			a[kx][ky]=1;
			if(b[kx][ky] == 'e'){
				flag = 1;
			}else{
				dfs(kx,ky);
			}
		}
	}
}

int main(){
	int k=1,sum;
	cin>>sum;
	while(k<=sum){
		memset(a,0,sizeof(a)); //将标记数组a全部记为 0，表示这个点未走过 
		cin>>n;
		for(int i = 0;i<n;i++){
			for(int j=0;j<n;j++)
				cin>>b[i][j];
		}
		for(int i = 0;i<n;i++){
			for(int j=0;j<n;j++){
				if(b[i][j]=='s')
					dfs(i,j); 
			}
				
		}
		if(flag==1){
			cout<<"YES"<<endl;
		}else{
			cout<<"NO"<<endl;
		}
		k++;
	}
	return 0;
} 

有不懂的地方或者有错误的地方欢迎评论批评指正。

DFS（深度优先搜索）
/*
DFS（深度优先搜索），“深度”是关键，以走迷宫为例，不撞南墙不回头，先找到最深的，然后回溯到上一个路口，以此类推。
有上述可知，DFS可由递归实现，所谓的南墙就是递归边界。
*/

//package app;

import java.util.Scanner;

class DFSTest{
    final static int maxn = 30;
    static int maxValue = 0;
    static int ans = 0;
    static int[] w = new int[maxn];  //用于存放每个点的质量
    static int[] c = new int[maxn];  //用于存放对应点的价值或者说权重
    static int n,V;      //n是有几点个点，V是能接受点的质量的最大总和
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        n = input.nextInt();      //输入有几个点
        V = input.nextInt();      //输入能存放最大点的质量的总和
        for(int i=0;i<n;i++){     //输入每个点的质量
            w[i] = input.nextInt();
        }
        for(int i=0;i<n;i++){
            c[i] = input.nextInt();//输入每个点的权重
        }
        input.close();
        dfs(0, 0, 0);
        dfs1(0, 0, 0);
        System.out.println(maxValue);
        System.out.println(ans);
    }

    public static void dfs(int index, int sumW, int sumC){//index是每个点对应的序号,sumW是质量总和，sumC是权重总和或者说是价值总和
        if(index == n){
            if(sumW <= V && sumC > maxValue){
                maxValue = sumC;
            }
            return;
        }
        dfs(index+1, sumW, sumC);
        dfs(index+1, sumW+w[index], sumC+c[index]);
    }

    public static void dfs1(int index, int sumW, int sumC){//剪枝后的DFS
        if(index == n){
            return;
        }
        dfs1(index+1, sumW, sumC);
        if(sumW + w[index]<=V){
            if(sumC + c[index] > ans){
                ans = sumC + c[index];
            }
            dfs1(index+1, sumW+w[index], sumC+c[index]);
        }
    }
}