深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。这种算法会尽可能深地搜索图的分支，直到找到目标节点或达到叶节点（没有子节点的节点），然后回溯到上一个分支继续搜索。DFS可以用于许多问题，比如路径寻找、连通性验证、拓扑排序等。

在ACM、蓝桥杯等著名竞赛中DFS算法是比较重要的，特别是在蓝桥杯中每一年几乎都要考DFS/BFS算法。DFS算法在OI赛中用处非常大，可以通过DFS/BFS暴力的方式可以拿到部分分数，蓝桥杯一般可以拿到20%的分数，有的甚至高达50%，是暴力得分的不二之选。

DFS通常使用递归或栈来实现。以下是DFS的基本步骤：

选择起始点：选择图中的一个点作为起始点。

访问节点：标记起始节点为已访问，并将该节点加入递归或栈中。

探索邻接节点：从该点周围取出一个点，检查它的所有未访问的邻接节点。

递归或迭代：对每个未访问的邻接节点，将其标记为已访问，然后将其推入递归或栈中。

回溯：当当前节点的所有邻接节点都被访问后，递归中回溯/从栈中弹出该节点，继续搜索上一个点的其他分支。

结束条件：当栈为空或找到目标节点时，搜索结束。

下面放一张我们学校ACM在大一培训时使用的一张动态BFS/DFS步骤图。注：红色遍历为BFS、黄色遍历为DFS。（绿色为起点，紫色为终点，黑色为障碍物）

由上图中我们可以看出，DFS的遍历为一条路，用我们学长的话说就是一条路走到头，找不到就再回头换另一条路，继续搜索，直到找到终点。那么BFS就是在一个点的周围每一个点都走一遍试一下，属于扩散型的。找不到的话在这个点的基础上再去扩散四周寻找。BFS一般通过栈来实现，DFS一般通过递归来实现。

下面我们将以3*3的网格，只考虑上下左右四个方向，上左、下左等四个方向不考虑，递归顺序为{上、下、左、右}，顺序可按照自己的想法，这里以上下左右顺序为例，给大家模拟实现一下过程。

本身就在起点，先把此时起点标记为已经走过了，即vis[起点]=true，告诉后面这个点不能再搜索了，不标记的话可能会陷入死循环。在寻找起点的上下左右格子，我们发现，{上}、{左}方向都已经超出了格子范围，在题中就是超出了下标范围，那么我们能考虑的就只有{下}、{右}方向，由于我们递归的顺序为{上、下、左、右}，{上}方向超出了格子范围，那么级别最高且合法的就是{下}方向了，从起点向下走。

先标记，vis[第一步]=true。此时我们发现{左}方向已经不在网格里面了，下标已经越界了，所以不考虑{左}方向，此时递归顺序为{上、下、右}方向，向上走，在第一步一开始我们就把vis[起点]标记为true，说明已经走过了，下面不允许走了，{上}方向也不能走了。此时优先级最高的为下方向了，下方向没有被标记过，所以可以走。

还是先标记，把当前位置所走的标记为已经走过，即vis[第二步]=true。此时我们发现{左、下}两个方向已经越界了，所以不考虑，此时递归优先级为{上、右}，由于第三步刚开始就把vis[第二步]=true，已经标记了，不能走了，所以这一步只能向右走。

还还还是先标记，vis[第三步]=true。此时我们发现{下}方向已经越界了，所以不考虑{下}方向了，在这一步刚开始我们把{左}方向这个点已经给标记过了，所以不能走，那么剩余的合法递归顺序为{上、右}，此时我们便可以向上走，找到终点，完成此次DFS(深度优先搜索)。

从上面的图解算法中步骤我们把算法步骤归结为一下：

首先我们需要一个数组即输入的数据数组，可能为int、也肯为char，在绝大部分题目中都需要一个标记数组，即bool类型的vis数组。然后在题目中找到搜索的起点跟终点，设置dfs函数的参数，根据题目的不同参数个数不同。在主函数dfs函数之前先把vis[起点]标记为true，一定不要忘记，否则就是死循环。确定了起点，把参数传给dfs函数参数，进入dfs递归函数，确定函数的终止条件，即当前状态==目标状态或者递归值==某个数等，终止条件一定在函数的最前面，否则会影响答案。再次，在当前点，寻找当前点的周围（根据题目，可能四个点，也可能八个点等），用for循环遍历每一个点，如果这个点已经被标记过了或者数组下标越界都是不合法的，直接continue掉。那么剩下的就是合法的，可以访问下一个点，先把下一个点给标记完再去递归下一个点，再进入dfs函数递归，注意大部分dfs都需要回溯的,即把vis[当前点]=false,为什么需要回溯，这就是我们所说的一条路走不通，回头换一条路走，那么我要回头，前面走过的已经被标记的，还咋走，那就要vis[当前点]=false解除标记。下面贴一个dfs函数的一般模板。

void dfs(int dep){//dep为当前状态
	if(dep==x){//当前状态==目标状态，终止条件
		更新结果
		return;
	}
	for(int i=0;i<n;i++){//遍历每一种可能
		if(不符合条件){
			continue;//跳过
		}
		//符合条件
		vis[访问的点]=true;//先标记
		dfs(下一个状态);
		vis[访问的点]=false;//恢复现场,大部分需要回溯,有的不需要这一步
	}
}

现在各大算法刷题网站上dfs题目非常的多，dfs题目的变化也比较多，现在各种各样的题目层出不穷，博主所做过的题印象中大部分在终止条件哪里变化的比较多，像是还有在条件判断上增加附加条件等等，下面博主选取几个比较具有代表性的给大家讲解一下，加深理解一下dfs算法。

马在中国象棋以日字形规则移动。请编写一段程序，给定n×m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。

第一行为整数T(T < 10)，表示测试数据组数。

每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标n,m,x,y。(0≤x≤n-1,0≤y≤m-1, m < 10, n < 10)。

每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，0为无法遍历一次。

1

5 4 0 0

32

这个题不同在了马走的方向跟之前走四个方向的不同他是斜着跳，与象棋上的马一样，例如（1，2）、（-2，1）等，初始状态就是起点（x,y），终点的话，除了起点每个点都可能是终点，这样不好确定终点，但是我们有一个条件，遍历完所有点，有两种方法可以确定遍历完所有点，第一种是n*m的棋盘，那么如果走完了n*m步就完成了一次，第二种设置一个标记数组，标记棋盘上每一个点都被标记完了就完成一次，很明显第一种方法比第二种好。由于统计的是途径总数，每完成一次计数就++,直到他无路可走，自动退出函数。

#include<iostream>
using namespace std;
int a[15][15],vis[15][15];
int n,m,sx,sy;
int ans;//途径数
int dx[]={1,1,-1,-1,2,2,-2,-2};//马在棋盘上可以跳八个方向
int dy[]={2,-2,2,-2,1,-1,1,-1};
void dfs(int x,int y,int dep){//（x,y）当前坐标，dep当前步数
	if(dep==n*m){//终止条件
		ans++;
		return;
	}
	for(int i=0;i<8;i++){//八个方向遍历
		int bx=x+dx[i];
		int by=y+dy[i];
		if(vis[bx][by]==1){//已经被标记过了
			continue;
		}
		if(bx<0||bx>=n||by<0||by>=m){//下标越界
			continue;
		}
		vis[bx][by]=1;//先标记该点
		dfs(bx,by,dep+1);//再去递归下一次
		vis[bx][by]=0;//回溯--解标记
	}
}
int main(){
	int t;
	cin>>t;
	while(t--){
		ans=0;
		scanf("%d%d%d%d",&n,&m,&sx,&sy);
		vis[sx][sy]=1;//起点标记
		dfs(sx,sy,1);
		printf("%d",ans);
	}
	
	return 0;
}

把 M个同样的苹果放在 N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

盘子相对顺序不同，例如 5，1，1和 1，5，1算作同一种分法。

输入包含多组测试数据。

每组数据占一行，包含两个整数 M 和 N。

每组数据，输出一行一个结果表示分法数量。

1≤M,N≤10;

7 3

8

N与M最大只有10，dfs可以适用，M个苹果放到N个盘子里，允许盘子空着不放，可以直接dfs递归实现，我们设置两个参数，一个遍历的盘子数dep,一个遍历的苹果数sum,每一次向盘子里面放t个苹果，那么苹果数sum-t，盘子数sum+1，当超出了盘子数不符合条件或者苹果数<0则返回上一步执行。

#include<iostream>
using namespace std;
 
int a[101]={1};//初始化为1放苹果的至少放一个
int m,n,num=0;//m:苹果，n:盘子
 
void dfs(int sum,int dep){
	if(sum<0){//没有苹果就没法放了，回溯
		return;
	}
	if(sum==0&&dep<=n+1){//终止条件
		num++;
		return;
	}
	for(int i=a[dep-1];i<=m;i++){//防止重复放比如{1，5，1}跟{5，1，1}是一样的放法
		a[dep]=i;//放的个数
		dfs(sum-i,dep+1);//继续搜索下一个盘子
        //没有回溯，因为这是组合问题，分的苹果数重复了属于同一种
	}
}
int main(){
    while(scanf("%d%d",&m,&n)!=EOF){
        num=0;
        dfs(m,1);
	    printf("%d\n",num);
    }
	return 0;
}

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。

如何将 8 个皇后放在棋盘上（有 8×8 个方格），使它们谁也不能被吃掉！

这就是著名的八皇后问题。

已经知道 8 皇后问题一共有 92 组解。

要求打印每一种解。

对于八皇后问题以后博主感觉不会出类似的题，但是我还是想把八皇后加入到例题来讲解，因为它实在是太经典了。八皇后问题是最经典的递归问题，你可以说没学过八皇后，但是不能说学了dfs但是不会八皇后。为什么说八皇后问题最经典，八皇后问题的条件一般是不会改变的，它在标记这一块动了手脚，本来由标记一个点变为标记整行、整列、点所在的主对角线、点所在的副对角线。主要麻烦在了标记这一块，标记处理好了，回溯的时候也比较好处理，现在对于标记网上有很多方法，我看了很多方法找出了一种我认为比较好的方法，是acking老师讲解的方法，跟大家分享一下。

首先，它需要标记四条线，分别是行、列、上左到右下、上右到左下，把它简化一下，我每次遍历从第一行开始，每次向下一个，这样保证了每次行不一样，可以少标记一个数组。列的话，一个一维vis数组就够了，上左到右下这条线，把它顺时针旋转45°，会发现是竖直的线。每一条线满足i-j+n不一样（i，j）是坐标。上右到左下这条线逆时针旋转45°，也会发现是一条竖线，每一条线满足i+j是不一样的。这样可以把它们的值当作下标值处理。

#include<stdio.h>
int a[10][10];
int vis1[8]/*标记列*/, vis2[16],/*标记左上右下*/ vis3[16]/*标记右上左下*/;
int n = 8, ans = 0;
void vis(int i, int j, int flag) {
	a[i][j] = flag;
	vis1[j] = flag;
	vis2[i - j + n] = flag;
	vis3[i + j] = flag;
}
void dfs(int i) {
	if (i == n) {
		printf("No.%d\n", ++ans);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				printf("%d ", a[i][j]);
			}
			printf("\n");
		}
		return;
	}
	for (int j = 0; j < n; j++) {
		if (vis1[j] == 0 && vis2[i - j + n] == 0 && vis3[i + j] == 0) {
			vis(i, j, 1);
			dfs(i + 1);
			vis(i, j, 0);
		}
	}
}
int main() {
	dfs(0);
	return 0;
}