专题五：DFS深度优先搜索
专题五：DFS深度优先搜索
目录
- 专题五：DFS深度优先搜索
- 前言
- 什么是回溯法
- 如何理解回溯法
- 回溯法解决的问题
- 回溯法模板
- 1 、回溯函数模板返回值以及参数
- 2、 回溯函数终止条件
- 3 、回溯搜索的遍历过程
- 回溯算法模板框架代码如下
- 递归实现指数型枚举
- 题目
- 代码及注释
- 方法一：递归枚举法（子集）
- 方法二：递归填坑法（每个数字选与不选）
- 题解
- 递归实现排列型枚举
- 题目
- 代码及注释
- 题解
- 递归实现组合型枚举
- 题目
- 代码及注释
- 题解
- 迷宫问题
- 题目
- 代码及注释
- 题解
- 01背包问题
- 题目
- 代码及注释
- 题解
- 八皇后
- 题目
- 代码及注释
- 题解
- 方格分割
- 题目
- 代码及注释
- 题解
- 组队
- 题目
- 代码及注释
- 题解
- 总结
前言
本专题将讲解算法竞赛中最常用的算法dfs深度优先搜索，也叫回溯搜索法或者“暴力搜索”法，也就是说在比赛的时候就算遇到没有思路的题，也可以用递归实现暴力搜索来骗分。有的同学可能会过多的去纠结一些概念，比如递归、暴力搜索、回溯法、dfs等，其实我们大可不必去纠结，因为dfs和回溯搜索法本身就是一个算法，是用递归操作来实现的，而“暴力搜索”则是民间赋予的称号！！ 以下内容，我统称为回溯法（我最喜欢的名字）！
什么是回溯法
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，也就是暴力搜索。
如何理解回溯法
回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！
因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。
递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。
递归里面嵌套着循环，为单层搜索逻辑。
回溯法解决的问题
回溯法，一般可以解决如下几种问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
回溯法模板
1 、回溯函数模板返回值以及参数
在回溯算法中，我的习惯是函数起名字为backtracking，这个起名大家随意。
回溯算法中函数返回值一般为void。
再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
void backtracking(参数)
2、 回溯函数终止条件
什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。
所以回溯函数终止条件伪代码如下：
if (终止条件) {
存放结果;
return;
}
3 、回溯搜索的遍历过程
在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
分享一张代码随想录的图
回溯函数遍历过程伪代码如下：
for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
回溯算法模板框架代码如下
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
下面将会列举一些例题以及真题。后续会继续出一期专门的练习题！
递归实现指数型枚举
题目
代码及注释
方法一：递归枚举法（子集）
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int n;
vector<vector<int>> result;
vector<int> path;
void backtracking(int n, int startIndex) {
result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
if (startIndex > n) { // 终止条件可以不加
return;
}
for (int i = startIndex; i <=n; i++) {
path.push_back(i);
backtracking(n, i + 1);
path.pop_back();
}
}
int main()
{
cin>>n;
backtracking(n,1);
//记住二维向量的输出方式！！
for(int i=0 ; i <result.size(); i ++ )//把所有方案输出
{
for(int j=0;j<result[i].size();j++)
{
printf("%d ",result[i][j]);
}
puts("");
}
}
📌本解法需要注意：子集必须再递归终止前收集 二维向量输出的方法要会
方法二：递归填坑法（每个数字选与不选）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 16;
int n;
int st[N]; // 状态，记录每个位置当前的状态：0表示还没考虑，1表示选它，2表示不选它
void dfs(int u)
{
if (u > n)
{
for (int i = 1; i <= n; i ++ )
if (st[i] == 1)
printf("%d ", i);
printf("\n");
return;
}
st[u] = 2;
dfs(u + 1); // 第一个分支：不选
st[u] = 0; // 恢复现场
st[u] = 1;
dfs(u + 1); // 第二个分支：选
st[u] = 0;
}
int main()
{
cin >> n;
dfs(1);
return 0;
}
题解
递归填与不填，关键在于先画出递归搜索树，思路也就显而易见了。
递归实现排列型枚举
题目
代码及注释
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10;//题目中N的范围是9，但我们如果下标想从1开始，那么多用一个，开10
int n;
//此题可以发现在搜索的时候还要保证每个数只搜索一次，要判断当前这个位置可以用的数有哪些，
//因此还要存一个新的状态used：表示每个数有没有被用过
int state[N]; // 用st[]表示当前的状态：0 表示还没放数，1~n表示放了哪个数
bool used[N]; // true表示用过，false表示还未用过
//注意变量如果定义成全局变量的话，初值会自动赋成0，如果定义成随机变量的话，初值是一个随机值
void dfs(int u)
{
if (u > n) // 边界：枚举完了最后一位，
{
for (int i = 1; i <= n; i ++ ) printf("%d ", state[i]); // 打印方案：只需要把当前每个位置输出出来
puts("");
return;
}
// 依次枚举每个分支，即当前位置可以填哪些数
for (int i = 1; i <= n; i ++ )//从小到大枚举
if (!used[i])//如果当前位置是没有用过的，表示当前位置可以填这个数，成为一个分支,等价于used[i]==false
{
state[u] = i;//标记，更新状态
used[i] = true;//标记，更新状态，因为此题递归时需要两个状态表示
dfs(u + 1);//递归下一步
// 恢复现场,两个状态都要恢复
state[u] = 0; //当然，在这里state[]状态数组其实可以不用恢复，因为会直接覆盖掉，但是为了更好的展现算法流程，方便初学者理解最好加上
used[i] = false;
}
}
int main()
{
scanf("%d", &n);
dfs(1);//从前往后枚举，函数里面写一个参数，表示当前枚举到第几位了
//因为state[]和used是全局变量了，所以不需要写到函数参数里面
return 0;
}
题解
对于全排列问题我们可以这样想，第1个位置可以放1~n任意一个数，第2个位置可以放除了放在第1个位置的数以外的任何一个数，以此类推。因此我们可以画出一个递归搜索树，用map[]来表示储存当前排列。DFS函数要记住当前处理的是第index个位置，从1到n进行遍历，看看这个数是否可以放在第index个位置，需要有一个判重数组hashtable[x]来记录x是否在排列里面。
递归实现组合型枚举
题目
代码及注释
#include<iostream>
#include<cstdio>
using namespace std;
const int N=30;
int way[N];
int n,m;
void dfs(int u,int start)
{
//剪枝
if(u+n-start<m) return;//正在选第u个数，已经选了u-1个数，还能选n-start+1个数
if(u>m)
{
for(int i=1;i<=m;i++)
printf("%d ",way[i]);
printf("\n");
return;
}
for(int i=start;i<=n;i++)
{
way[u]=i;
dfs(u+1,i+1);
//way[u]=0;
}
}
int main()
{
cin>>n>>m;
dfs(1,1);
return 0;
}
题解
DFS的思路是这个样子的，假设当前处理的是第index个位置，这个位置可以放置start~n其中任意一个数。接着处理第index+1个位置，这个位置可以放置的最小数是前一位数的下一个数。即i+1~n
迷宫问题
题目
代码及注释
#include<bits/stdc++.h>
using namespace std;
const int N=100;
int dx[4]={0,0,-1,1};//定义上下左右四个方向
int dy[4]={1,-1,0,0};
int n,m,t;
int sx,sy,fx,fy,l,r;
int ans;
bool visited[N][N];
int ditu[N][N];
bool check(int x,int y)
{
if(x<1||x>n||y<1||y>m) return false;//下标越界
if(ditu[x][y]) return false;//有障碍物
if(visited[x][y]) return false;//已经访问过该点
return true;
}
void dfs(int x,int y)
{
if(x==fx&&y==fy)
{
ans++;
return ;
}
for(int i=0;i<4;i++)
{
int newx=x+dx[i];//走到下一个点
int newy=y+dy[i];
if(check(newx,newy))
{
visited[x][y]=true;
dfs(newx,newy);
visited[x][y]=false;
}
}
}
int main()
{
cin>>n>>m>>t;
cin>>sx>>sy>>fx>>fy;
while(t--)
{
cin>>l>>r;
ditu[l][r]=1;
}
dfs(sx,sy);
cout<<ans<<endl;
return 0;
}
题解
迷宫问题是拿来练习DFS与BFS很经典的题目。迷宫问题有很多种问法，比如迷宫从起点到终点有没有路径，有几条，最短路径是多少。
求从起点到终点的方案数显而易见也是要用DFS，遍历所有的情况。我们要考虑这样一个问题，迷宫里的某点(x,y)是否要被访问呢。当这点是障碍物肯定不能访问，该点不在迷宫里面也不能访问，该点访问过了那就不能访问了。(题目中有每个方格最多经过一次)。因此我们需要一个check()函数来判断某一点是否合法。合法我们就去访问该点。
其实这个过程就是一个剪枝的过程，根据题目条件限制，剪掉一些不可能存在解的分支。
另外我们该如何知道某点是障碍点呢，可以设置一个map数组来表示该迷宫。
当map[x][y]==1时表示该点是障碍点map[x][y]==0表示该点是正常点
01背包问题
题目
代码及注释
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int w[N], c[N];
int a[N][N];
int ans;
//由于记录了index不会出现重复遍历的问题，不需要额外的标记数组
void dfs(int index,int sumv,int sumc)
{
if(index==n)
{
if(sumv<=m)
{
ans=max(ans,sumc);
}
return ;
}
//只有两种情况不需要for循环了
dfs(index+1,sumv+w[index],sumc+c[index]);//选第i个物品
dfs(index+1,sumv,sumc);//不选第i个物品
}
int main()
{
cin>>n>>m;
for (int i = 0; i < n; i++)
{
cin >> w[i] >> c[i];
}
dfs(0,0,0);
cout<<ans<<endl;
return 0;
}
题解
第i件物品无非就是选和不选两种情况，在搜索的过程中DFS函数必须要记录当前处理的物品编号index，当前背包的容量sumW，当前的总价值sumC。
当不选第index个物品时，那么sumW,sumC是不变的，接着处理第index+1个物品，也就是DFS(index+1, sumW, sumC)。
当选择第index个物品时，sumW变成sumW+w[index]，sumC变成sumC+v[index]，接着处理第index+1个物品，也就是DFS(index+1, sumW+w[index],sumC+v[index])。边界条件也就是把最后一件物品也处理完了，即index=n（注意默认index从0开始）。
当一条分支结束了该干什么呢，很简单呀就是判断该分支最终满不满足总重量不大于背包容量。即sumW<=v。满足的话我们就更新价值maxvalue，即maxvalue=max(maxvalue,sumC）
八皇后
题目
代码及注释
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=100;
int a[100],b[100],c[100],d[100];
int ans;
bool check(int i,int j)
{
if(!b[j]&&!c[j-i+n]&&!d[i+j]) return true;//注意这里的对角线表达式只能为这个
return false;
}
void dfs(int i)
{
if(i>n){
ans++;
if(ans<=3){
for(int i=1;i<=n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
return ;
}
for(int j=1;j<=n;j++)//枚举一行中所有列的棋子
{
if(check(i,j))
{
a[i]=j;
b[j]=1;
c[j-i+n]=1;
d[i+j]=1;
dfs(i+1);
b[j]=0;
c[j-i+n]=0;
d[i+j]=0;
}
}
}
int main()
{
cin>>n;
dfs(1);//从第一行开始枚举
cout<<ans<<endl;
return 0;
}
题解
这道题DFS的思路还是比较清晰的，每行有且只有一个棋子，那么DFS可以记录下当前处理的是第几行的棋子。假设当前处理的是第i行的棋子，那么要枚举处在该行的棋子位置，判断哪个是合法的。
什么样的位置算是合法的呢，这个位置的列还有左对角线，右对角线位置都不能有棋子。那么又该如何表示这些位置呢？我们采用一维数组来分别表示列，左对角线，右对角线。列很好表示就是b[j]，左对角线我们可以发现行减去列的绝对值是恒定的，即c[i-j+n],右对角线行加列是恒定的。即d[i+j]。
方格分割
题目
代码及注释
#include<bits/stdc++.h>
using namespace std;
int maze[7][7];//表示已经访问过的点，1表示已经访问的
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int ans;
void dfs(int x,int y)
{
if(x==0||y==0||x==6||y==6)
{
ans++;
return ;
}
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(maze[a][b]!=1)
{
maze[a][b]=1;
maze[6-a][6-b]=1;
dfs(a,b);
maze[a][b]=0;//回溯
maze[6-a][6-b]=0;
}
}
}
int main()
{
maze[3][3]=1;//中心点 标记已经访问
dfs(3,3);
cout<<ans/4<<endl;//旋转对称只算一种方式
return 0;
}
题解
本题需要发现一个规律：分割成的两部分一定是中心对称的，也就是从中心点开始上下左右搜索的结果就是答案，但是需要记录已经搜索过的点，以及旋转对称只算一种方式。
画个图会清晰很多，写出点的坐标，并算出中心对称的坐标。
组队
题目
代码及注释
#include<bits/stdc++.h>
using namespace std;
int maze[20][20];
bool visited[20];
int ans;
void dfs(int index,int sum)
{
if(index==5)//枚举当前是第几位,固定列
{
ans=max(ans,sum);
return ;
}
for(int i=0;i<20;i++)//枚举每一行
{
if(maze[i][index]!=0&&!visited[i])
{
visited[i]=true;
dfs(index+1,sum+maze[i][index]);
visited[i]=false;a
}
}
}
int main()
{
for(int i=0;i<20;i++)
for(int j=0;j<5;j++)
cin>>maze[i][j];
dfs(0,0);
}
题解
本题是经典的dfs模型，可以看成是排列问题，对于一号位来说有20种选择，对于二号位来说有19种选择，也就是说可以维护当前正在选择第index位，每一次dfs更新一个最大值。
纵向递归：index代表第几位
横向枚举：一共有20个选手，for循环枚举。
参数：index sum
回溯数组：visited[N] 表示已经访问过的选手
总结
本文主要讲解了回溯搜素算法的原理、模板以及具体的代码与例题。需要大家熟练掌握算法，多做练习题，才能在比赛中灵活运用该算法。预祝各位考出好成绩！！
