解析DFS（持续更新中）

大家好，欢迎来到IT知识分享网。

DFS介绍：

DFS 全称是 Depth First Search ，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。

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[],n; bool book[];//判断是否被访问 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; }

例3

遍历图

DFS本来就是图算法！最朴素的用法也是用来遍历图了。

//这里是从点①开始遍历 你也可以从其他点开始遍历

思路：从第一个点开始，分别询问其他点 如果其他点没有被访问，就去访问，然后进而从该访问点继续向其他点访问，以实现“深度搜索”。

#include<cstdio> #include<iostream> using namespace std; typedef unsigned long long ll; #define inf  int mp[101][101]; bool book[101]; int sum=0,n,m; void dfs(int cur){ cout<<cur<<' '; sum++; if(sum==n) return; else{ for(int i=1;i<=n;i++) { if(!book[i] && mp[cur][i]==1) { book[i]=true; dfs(i); } } } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j) mp[i][j]=0; else mp[i][j]=inf; for(int i=1;i<=m;i++) { int u,v; cin>>u>>v; mp[u][v]=mp[v][u]=1; } book[1]=true; dfs(1); return 0; } /* input 5 5 1 2 1 3 1 5 2 4 3 5 output 1 2 4 3 5 */

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可以逐个枚举接下来要到的结点。

记忆化搜索

记忆化搜索能够大大优化DFS！放些例题以供参考qwq

T1

滑雪

分析：直接dfs无疑会超时，而在搜的时候添加数组记录则会起到优化的效果

AC code（无头文件）

 int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; int map[105][105]; int m,n; int dp[105][105];//记录从x,y点滑下来的时候最长路 int ans=-1; int dfs(int x,int y){ if(dp[x][y]>0) return dp[x][y]; //如果被记录过直接返回 dp[x][y]=1; for(int i=0;i<4;i++){ int kx=x+dx[i]; int ky=y+dy[i]; if(map[kx][ky]>=map[x][y]||kx<1||ky<1||kx>n||ky>m) continue;//"障碍" dp[x][y]=max(dp[x][y],dfs(kx,ky)+1); } return dp[x][y]; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&map[i][j]); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ ans=max(ans,dfs(i,j)); } } cout<<ans<<endl; return 0; }