DFS介绍：
DFS 全称是 Depth First Search ，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。
该算法讲解时常常与 BFS 并列，但两者除了都能遍历图的连通块以外，用途完全不同，很少有能混用两种算法的情况。
DFS 最显著的特征在于其递归调用自身 。同时与 BFS 类似，DFS 会对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以确保 每个点仅访问一次 。符合以上两条规则的函数，便是广义上的 DFS。
DFS的思路：所谓深度优先，就是说每次都尝试向更深的节点走。
DFS优化：DFS是暴搜，改写成记忆化搜索之类的，或者剪枝（break一些分支）都可以优化（待补充）。
DFS的板子大致如下：
void dfs(int step)
{
if(走到边界)
{
操作();//输出答案等
return;
}
else
{
for()//枚举方向等
if(满足进一步搜索条件)
{
标记为访问;
search(step+1);
收回标记;//回溯
}
}
}
这个板子看上去比较易懂，但其细节还是值得思考的，下面以几个经典题目为例子，解析DFS相关语句。
例题1：求1-n全排列
这是DFS求全排列的板子，喜欢的可以点击拿走（
题目大意：就是求1-n全排列
首先，我们可以模拟一下求全排列这个过程（参考了《啊哈！算法》）
这里模拟n=3的情况
我们有三张卡牌1,2,3 并且有三个卡槽，现在要将三张牌放入三个卡槽中，从第一个卡槽开始出发，首先我们向第一个卡槽放入1，然后继续向前走，依次放入2,3，并向前走（到第三个卡槽后一步），此时，得到了第一个序列1,2,3。（灵魂配图预警）
而且，我们的手中已经没有卡牌了，所以要回退，在回到第三个卡槽的时候，收回第三张牌（这里是3），然而此时若放下3便和刚才的情况重复，于是继续回退收回第二张牌（这里是2）。在完成收回第二张牌的动作之后，我们手上有了2,3。于是便可以将3放入第二个卡槽，向前走，将2放入地三个卡槽，得到第二个序列1,3,2。
类似地，可以得到1-3的全排列。
模拟完后我们就可以轻松写出代码了
现在上代码：（先看看注释理解一下吧）
#include<iostream>
using namespace std;
int a[100001],n;
bool book[100001];//判断是否被访问
void dfs(int step){
// if(满足所需要的条件) { 相应的操作；return；}
if(step==n+1){
for(int i=1;i<=n;i++) printf("%d ",a[i]);//打印
cout<<endl;
return;
}
//枚举
for(int i=1;i<=n;i++)
{
if(book[i]==0)
{
a[step]=i;//记录数据
book[i]=1;//记录相应的数已经被访问
dfs(step+1);//进一步搜索
book[i]=0;//恢复到未被访问
}
}
}
int main(){
cin>>n;
dfs(1);//从一开始搜索并且打印
return 0;
}
很多语句都是很好理解的，但是不是还是一头雾水
那么只要解决几个难懂的问题就可以了
现在需要解析的是：
Q1：这个函数实现了什么？
先撇开判定搜完一轮的if语句，这个函数其实就是for循环套着for循环，他的本质其实与n个for循环无异，但是为什么要这样子写？就是因为n可能很大，用for一直写可能实现不了。所以这个函数的功能就是暴力依次枚举1-n的全排列（可以试试n=3只用for循环实现就可以理解了）。
Q2：如下，这里的return语句到底返回到了哪里？
// if(满足所需要的条件) { 相应的操作；return；}
if(step==n+1){
for(int i=1;i<=n;i++) printf("%d ",a[i]);//打印
cout<<endl;
return;
}这个问题困扰了我很久，在被dalao教做人与dalao讨论后，我得到了较为清楚的解释。
return的作用无非是返回，结束该层的函数，而在这个函数中，便是结束了一个dfs(n+1),回到了dfs(n)中（第n层循环），并继续执行dfs(n)中的语句，比如这里是回到第二个语句中：
1 dfs(step+1);
2 book[i]=0;//恢复到未被访问 拿刚才的模拟过程来说：就是我们已经走到第三个卡槽之后，开始回退。
Q3：为什么回退之后拿回第一张牌（比如模拟中的第三个卡槽的牌）之后，不会出现立即将该牌放入相应卡槽出现死循环的现象呢？
以模拟过程为例，回到程序中，不难发现，此时的循环中的i=4，已经跳出这层循环了，自然地，回到了上一层循环（也就是第二个卡槽中，实现了回退）。
（待补充）
解决了这些问题之后，大概就能够比较清楚地了解DFS的工作原理了。
下面用递归树来刻画DFS实现的过程以加深理解（以求1-3的全排列为例）：
前方灵魂图示预警
从第一个结点出发，开始搜索~
根据DFS的思路，搜到无路可走开始回退。
类似地，继续往下搜，直到得到所有答案：
例2：迷宫
题目大意：就是给你一个迷宫（废话），迷宫有一些障碍，需要你求从起点坐标到终点坐标的方案总数。
题目链接
下面贴出代码以供参考：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
int map[10][10];//存图
int x,y;//记录起点坐标
int px,py;//记录终点坐标
int m,n,t;
int a,b;//记录障碍点
ll ans=0;//初始化ans
const int dx[4]={0,0,-1,1};//x direction
const int dy[4]={1,-1,0,0};//y direction
void dfs(int x,int y){
if(x==px&&y==py)//到达终点
{
ans++;
return;
}
else{
for(int i=0;i<4;i++)
{
int kx=x+dx[i];int ky=y+dy[i];//进行移动
//判定是否越界 有障碍 已经访问过
if(kx<1||ky<1||kx>m||ky>n||map[kx][ky]==1||map[kx][ky]==2)continue;
map[kx][ky]=1;//标记已经访问
dfs(kx,ky);
map[kx][ky]=0;
}
}
}
int main(){
cin>>n>>m>>t;
cin>>x>>y;cin>>px>>py;
while(t--){
cin>>a>>b;
map[a][b]=2;
}
map[x][y]=1;//初始化，标记起点为已经访问
dfs(x,y);//从起点开始搜
cout<<ans;
return 0;
}DFS易错点
初学DFS，很容易会写出bug，这里就放一些出现错误的代码供读者阅读、修改，同时我也会贴出正确代码并加以解析。
例1：租用游艇（题目请点击下面的链接~）
https://www.luogu.com.cn/problem/P1359
解析：这道题本来不是DFS解的题，但是用DFS+剪枝也能够过，所以就贴出来了~
思路：这题其实就是求最短路，不懂的可以画一下图。我们只需要暴搜将所有的路径长度求出并不断更新答案就可以了。
图示:
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
int map[201][201]; //map[i][j]:结点i->j的键值
int ans=1e7;//初始化ans为足够大
int n;
void dfs(int step,int temp){
if(temp>ans) return;//剪枝
if(step==n){
ans=min(ans,temp);//更新答案
return;
}
for(int i=step+1;i<=n;i++){
step=i;
dfs(step,temp+map[step][i]);
}
}
int main(){
cin>>n;
for(int i=1;i<=n-1;i++)
{
for(int j=i+1;j<=n;j++)
{
scanf("%d",&map[i][j]);
}
}//读入
dfs(1,0);
cout<<ans<<endl;
return 0;
}请读者先看看上面的代码有什么问题。
问题出在这里：
for(int i=step+1;i<=n;i++){
step=i;
dfs(step,temp+map[step][i]);
}如果将step赋值为i，那么循环的时候会出现问题。
而改成这样：
for(int i=step+1;i<=n;i++){
dfs(i,temp+map[step][i]);
}便可以保证循环的正常进行，因为在这层for中，i可以逐个枚举接下来要到的结点。
