目录
- 搜索算法（深度优先搜索DFS和广度优先搜索BFS）以及典型算法例题
- 深度优先搜索 （Depth First Search 简称 DFS）
- DFS 的设计步骤
- 深度优先搜索（DFS）算法例题
- 例题一：N皇后问题
- 例题二：路径之谜问题
- 例题三：最大数字
- 广度优先搜索（Breadth First Search 简称 BFS）
- 广度优先搜索基本概念
- 广度优先搜索（BFS）算法例题
- 例题一：长草问题
- 例题二：走迷宫问题
【数据结构与算法】系列文章链接: 【数据结构与算法】递推法和递归法解题（递归递推算法典型例题）
【数据结构与算法】系列文章链接: 【数据结构与算法】C++的STL模板（迭代器iterator、容器vector、队列queue、集合set、映射map）以及算法例题
【数据结构与算法】系列文章链接: 【数据结构与算法】二分查找算法
搜索算法（深度优先搜索DFS和广度优先搜索BFS）以及典型算法例题
深度优先搜索 （Depth First Search 简称 DFS）
注意：深度优先搜索算法（DFS）的时间复杂度较高，深度优先搜索是 O(n!) 的阶乘级算法，它的效率非常低，在数据规模变大时，此算法就难以解决当前的问题了。
DFS 的设计步骤
- 确定题目的状态以及边界
- 确定状态的转移方式
- 找到问题的出口，计数或某个状态
- 设计搜索
DFS的通用模板
int check(这里输入相关参数){
if(condition)//括号中写上对应的满足条件
return 1;//满足条件后输出 1
return 0;
}
bool pd(输入判断的相关参数){
//根据题中 进行具体的操作
}
void dfs(int step)
{
//判断边界pd()
{
//不在边界内，即回溯
}
//尝试每一种可能
{
//满足check条件
//标记
//继续下一步
dfs(step+1)；
//恢复初始状态（回溯的时候要用到）
}
}
深度优先搜索（DFS）算法例题
例题一：N皇后问题
输入示例：
5
输出示例：
10
题目分析：
- 第一步：
设：当前行为第一行，当前列为第一列，从第一列开始搜索，即只能让皇后从第一行放到第n行。
这样做的好处是，我们不需要去判断皇后是否同行，我们只需要去判断皇后是否在斜线和是否同列就行。 - 判断边界
在当前行，当前列的位置上判断是否满足条件（也就是保证经过这一点的行，列与斜线上都没有两个皇后），如果不满足，跳到第五步（不符合边界条件）
判断条件为：
我们使用数值x[a]=i来表示第a个皇后的位置在第a行的第i列。
判断是否同列的方法是：循环判断x[a]==x[i]是否为真。
判断是否在同一斜线上的方法：循环判断abs(x[k]-x[i]) == abs(k-i)是否为真 - 搜索过程
调用check()函数
如果完成（满足）题意的任务 加一，就继续调用函数 放下一个皇后 check()函数
如果搜索到第N+1行的时候。求得结果 （可行方案数量）记录加一。- 当前位置不满足，进行回溯。
边界判断函数PD(int k) 判断是否越界：
int PD(int k)//边界判断
{
for(int i=1; i<k; i++)
{
if(abs(k-i)==abs(x[k]-x[i]))
return 0;
else if (x[k]==x[i])
return 0;
//即判断是否符合条件来放,i表示皇后所在的行数，x[i]表示所在的列数，
//所以前面那个条件用来判断两个皇后是否在对角线上,后面用来判断是否在同一列上。
//行数不需要判断，因为他们本身的i就代表的是行数
}
return 1;
}
检查是否完成题中任务的函数check(int a)：
bool check(int a)
{
if(a>n)
sum++;
else
return 0;
return 1;
}
深度优先搜索的函数 DFS(int a)：
void DFS(int a)
{
if(check(a))
return ;
else
for(int i=1; i<=n; i++)
{
x[a]=i;
//第a个皇后放的列数
if(PD(a))
//判断是否能放这步
DFS(a+1);
//能的话进行下一个皇后的放置
x[a]=i;
else continue ;
//不能就下一列
}
}
题解代码示例：
#include <iostream>
#include <cstdio>
using namespace std;
int x[15] = {0};//数组稍微建立大一点 防止某些不影响结果的越界报错
int sum,n;//
int PD(int k)//边界判断
{
for(int i=1; i<k; i++)
{
if(abs(k-i)==abs(x[k]-x[i]))
return 0;
else if (x[k]==x[i])
return 0;
//即判断是否符合条件来放,i表示皇后所在的行数，x[i]表示所在的列数，
//所以前面那个条件用来判断两个皇后是否在对角线上,后面用来判断是否在同一列上。
//行数不需要判断，因为他们本身的i就代表的是行数
}
return 1;
}
//检查
bool check(int a)
{
if(a>n)
sum++;
else
return 0;
return 1;
}
void DFS(int a)
{
if(check(a))
return ;
else
for(int i=1; i<=n; i++)
{
x[a]=i;
//第a个皇后放的列数
if(PD(a))
//判断是否能放这步
DFS(a+1);
//能的话进行下一个皇后的放置
x[a]=i;
else continue ;
//不能就下一列
}
}
int main()
{
cin>>n;
//表示几个皇后
DFS(1);
//每次都从第一个皇后开始
cout<<sum<<endl;
return 0;
}
例题二：路径之谜问题
输入示例：
4
2 4 3 4
4 3 3 3
输出示例;
0 4 5 1 2 3 7 11 10 9 13 14 15
题目分析：
方法一：采用逆推法，逆向思维，从终点开始走，每走一格拔下来一个箭（采用方法一 判断条件方便）
方法二：走一格射两个箭。
-
设当前位置为第一行，当前列为第一列从左上角开始搜索（寻路）。
-
判断边界：
在当前行，当前列的位置上判断是否满足条件，若不满足条件跳到第五步。
判断条件：
flag[x][y]==1标记数组已经被走过
x<1 || x>n || y<1 || y>n分别表示从左侧走出方格、从右侧走出方格、从上出走出方格、从下处走出方格
col[x]<=0箭用完了
rol[y]<=0箭用完了 -
搜索过程
调用check()函数。判断是否走到终点，如果走到终点是否完成任务 -
check()函数：
如果当搜索到x=n,y=n时，且箭靶上的箭都没了 -
在当前位置上不满足条件的情况，进行回溯，并且还原现场。
check()函数：判断是否走到终点，如果走到终点是否完成任务
bool check(int x, int y) //判断走过的路径的箭靶数是否与目标相同
{
if(x==n && y==n)//走到了终点
{
for(int i=1; i<=n; i++)
{//判断每一列是否为零
if(col[i]!=0)
{
return false;
}
//如果箭靶上的数目不为0，根据逆推，我们通过当前路径得不到箭靶上的结果
}
for(int i=1; i<=n; i++)
{//判断每一行是否为零
if(rol[i]!=0)
{
return false;
}
//如果箭靶上的数目不为0，根据逆推，我们通过当前路径得不到箭靶上的结果
}
//如果都为零了 就说明这条路对了 然后把这条路线输出出来
for(int i=0; i<res.size(); i++)
{
int x=res[i].first;
//x 轴坐标
int y=res[i].second;
//y 轴坐标
int sum=n*(x-1)+y-1 ;
// 通过计算的到为题目要求的坐标系
cout <<sum<< " ";
}
cout << endl;
return false;
// 成功终止
}
//没走到终点
return true; //继续搜索
//关于终止还是继续我们交给判定即可
}
判断是否超出边界的函数pd()：
//边缘判断条件
bool pd(int x2,int y2) //边界判断
{
if(flag[x2][y2]==1)
return 0;
//已被走过，不能再走，超出边界
else if(x2<1)
return 0;
//从左侧走出方格
else if(x2>n)
return 0;
//从右侧走出方格
else if(y2<1)
return 0;
//从上侧走出方格
else if(y2>n)
return 0;
//从下侧走出方格
//剪枝
else if(col[x2]<=0)
return 0;
//没走到右下角，箭用完了
else if(rol[y2]<=0)
return 0;
//没走到右下角，箭用完了
else return 1;
//符合边界条件，可以继续执行搜索
}
#include <bits/stdc++.h>
using namespace std;
struct PII
{
int first;//x坐标
int second;//y坐标
};
const int N = 30;
int rol[N];//行 也就是y轴
int col[N];//列 也就是x轴
int n;//格子数 长宽从1到n
bool flag[N][N]; //用来标记是否走过
vector<PII> res;//
//---------图的路径搜索常用方向移动表示-------
int dx[4]= {0,1,-1,0};
int dy[4]= {1,0,0,-1};
//我们做一下约定：
// 两两组合形成上下左右四个方向
// 1------------------> x
// |
// |
// |
// |
// |
// |
// |
// ↓
// y
// dx[0]=0 dy[0]=1 那么代表向下的方向
// dx[1]=1 dy[1]=0 那么代表向右的方向
// dx[2]=-1 dy[0]=0 那么代表向左的方向
// dx[3]=0 dy[1]=-1 那么代表向上的方向
//--------------------------------------------
bool check(int x, int y) //判断走过的路径的箭靶数是否与目标相同
{
if(x==n && y==n)//走到了终点
{
for(int i=1; i<=n; i++)
{//判断每一列是否为零
if(col[i]!=0)
{
return false;
}
//如果箭靶上的数目不为0，根据逆推，我们通过当前路径得不到箭靶上的结果
}
for(int i=1; i<=n; i++)
{//判断每一行是否为零
if(rol[i]!=0)
{
return false;
}
//如果箭靶上的数目不为0，根据逆推，我们通过当前路径得不到箭靶上的结果
}
//如果都为零了 就说明这条路对了 然后把这条路线输出出来
for(int i=0; i<res.size(); i++)
{
int x=res[i].first;
//x 轴坐标
int y=res[i].second;
//y 轴坐标
int sum=n*(x-1)+y-1 ;
// 通过计算的到为题目要求的坐标系
cout <<sum<< " ";
}
cout << endl;
return false;
// 成功终止
}
//没走到终点
return true; //继续搜索
//关于终止还是继续我们交给判定即可
}
//边缘判断条件
bool pd(int x2,int y2) //边界判断
{
if(flag[x2][y2]==1)
return 0;
//已被走过，不能再走，超出边界
else if(x2<1)
return 0;
//从左侧走出方格
else if(x2>n)
return 0;
//从右侧走出方格
else if(y2<1)
return 0;
//从上侧走出方格
else if(y2>n)
return 0;
//从下侧走出方格
//剪枝
else if(col[x2]<=0)
return 0;
//没走到右下角，箭用完了
else if(rol[y2]<=0)
return 0;
//没走到右下角，箭用完了
else return 1;
//符合边界条件，可以继续执行搜索
}
void dfs(int x,int y)
{
if(!check(x,y))
{
return ;
//包含不符合规则的地方，回溯，用于剪枝
}
else
{
for(int i=0; i<4; i++)
{
int xt=dx[i]+x;
int yt=dy[i]+y;
if(!pd(xt,yt))
{
continue ;
//不符合要求继续换方向搜索
}
else
{
//因为要进行位置转移，我们给它起个名字，叫作案现场
//比如向下移动
flag[xt][yt]=true;
col[xt]--;
rol[yt]--;
res.push_back({xt,yt});
dfs(xt,yt);
//搜索回溯后，因为没有找到正确答案，所以要回复作案现场，返回到搜索之前
res.pop_back();
flag[xt][yt]=false;
col[xt]++;
rol[yt]++;
}
}
}
}
int main()
{
cin >> n;
for(int i=1; i<=n; i++)
cin >> rol[i];
for(int i=1; i<=n; i++)
cin >> col[i];
flag[1][1]=true;
col[1]--;//先拔一根箭
rol[1]--;//先拔一根箭
res.push_back({1,1});
dfs(1,1);
return 0;
}
例题三：最大数字
输入样例：
123 1 2
输出样例：
933
题目分析：
从左到右以此判断，从左边开始枚举。处理的时候的目的就是保证当前正在处理的数尽可能的变大。
使用的时候对于一个数要么使用方法一，要么使用方法二，因为它们是抵消的效果。
对于一个数字:
**操作二的使用情况：**如果这个数大于m（操作二的最大执行次数）,那么就没必要执行操作二了，这样反而让这个数据更小。因此执行操作二的条件是:x<m.
**操作一的使用情况：**如果这个数据x>=m我们就执行操作一，一直加尽量加到9，那么需要进行 9-x 次 操作一。当然可能此时 1 号操作并不足以让我们将 x 变成 9，但我们还是使用剩余的全部的次数将其变大，也就是变为x+t。因此，本次使用了操作一的次数为t=min(n,9-x).
题解代码示例：
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
char c[20];
LL ans=0;
//n:1号操作剩余次数 m:2号操作剩余次数
int n,m;
void dfs(int i,LL v){
//从左往右
int x=c[i]-'0';//数据转化
if(c[i]){//检查 c[i] 是否存在且不为空字符
//应该使用的操作次数
int t=min(n,9-x);
n-=t;
dfs(i+1,v*10+x+t);//递归调用
//回溯
n+=t;
//考虑操作2是否能够使用
//目的是减小到9
if(m>x){//只有在m>x 的情况下才使用
m-=(x+1);
dfs(i+1,v*10+9);//递归调用
//回溯
m+=(x+1);
}
}
else{
//答案取max
ans=max(ans,v);
}
}
int main()
{
scanf("%s%d%d",c,&n,&m);
dfs(0,0);
printf("%lld\n",ans);
return 0;
}
方法二：（方法二存在样例不通过的情况 ）
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
char c[20];
LL ans=0;
//n:1号操作剩余次数 m:2号操作剩余次数
int n,m;
void find_max(int i,LL v){
//从左往右
int x;//数据转化
int t;
//用的是字符串 '\0'
while(c[i]){//检查 c[i] 是否存在且不为空字符
x=c[i]-'0';//转换数字
if(m<=x){//如果这个数 大于或等于 减一的操作次数
//应该使用的操作次数
t=min(n,9-x);//
n-=t;
v=v*10+x+t;//记录下来 x+t 加完后的数
i++;
ans=max(ans,v);
}
//考虑操作2是否能够使用
//目的是减小到9
else{
v=v*10+9;
m-=(x+1);
i++;
ans=max(ans,v);
}
}
}
int main()
{
scanf("%s%d%d",c,&n,&m);
find_max(0,0);
printf("%lld\n",ans);
return 0;
}
广度优先搜索（Breadth First Search 简称 BFS）
广度优先搜索（Breadth First Search，简称BFS）：从某个状态开始，将所有节点加入一个先进先出的队列，然后一层层进行状态转移，并且展开节点。
广度优先搜索基本概念
伪代码：
int check(参数)
{
if(满足条件)
return 1;
return 0;
}
bool pd(参数){
相应操作
}
void bfs()
{
1. 把根节点放入队列尾端
2. 每次从队列中取出一个节点
3. Check 判断是不是答案，如果是结束算法 return;
4. 把当前取出的节点扩展，如果扩展后的节点经Pd()后符合要求，就放入队列，不符合就不放。
5. 转到步骤2，循环执行
}
如果所有节点被扩展完了，没有找到答案就无解。
广度优先搜索（BFS）算法例题
例题一：长草问题
输入示例：
4 5
.g...
.....
..g..
.....
2
输出示例：
gggg.
gggg.
ggggg
.ggg.
解题思路：使用 N × M N×M N×M 的矩阵来表示草地。
- 将字母g的位置加入队列
- 判断边界：
判断是否长草，是否超出范围 - 搜索
不断从队列中取出一个节点，进行上下左右的扩展，执行2的判断边界条件，符合的就放入队列，不符合就跳过。
执行K次扩展，输出草地状态 check()函数：
本题输出最终状态 因此不用这个函数
在广度优先搜索（BFS）中，我们通常需要对队列中的节点进行扩展，也就是对当前节点的邻居节点进行处理。处理完一个节点后，我们应该将其从队列中移除，以避免重复处理相同的节点，确保每个节点只被处理一次。
因此需要：
tempPair = q.front();
q.pop();
//这两步是取出队首的节点
题解代码示例：
#include <bits/stdc++.h>
using namespace std;
const int M = 1005;
struct PII//坐标
{
int first;
int second;
};
// C++ 有个数据类型叫 pair 上面的就可以定义为 pair<int,int> 用起来比较方便。
PII tempPair;//临时结点
char Map[M][M];
//---------图的路径搜索常用方向移动表示-------
int dx[4]= {0,1,-1,0};
int dy[4]= {1,0,0,-1};
// 两两组合形成上下左右四个方向
// 1------------------> x
// |
// |
// |
// |
// |
// |
// |
// ↓
// y
// dx[0]=0 dy[0]=1 那么代表向下的方向
// dx[1]=1 dy[1]=0 那么代表向右的方向
// dx[2]=-1 dy[0]=0 那么代表向左的方向
// dx[3]=0 dy[1]=-1 那么代表向上的方向
int n;// n 行
int m;// m 列
int k;// k 次
//记录 坐标位置
queue<PII > q; //广度优先搜索所用的队列
int len;//记录节点数量方便后续k的计算
bool pd(int x, int y)
{
if(x<1)
return 0;
// /x 轴坐标 左侧越界
else if(x>n)
return 0;
//x 轴坐标 右侧越界
else if(y<1)
return 0;
//y 轴坐标 上侧越界
else if(y>m)
return 0;
//y 轴坐标 下侧越界
else if(Map[x][y]=='g')
return 0;
//已经长草了
else return 1;
// 在范围内，且没长草
}
void BFS()
{
//BFS
//记得 层次
while(!q.empty()&&k>0)
{
tempPair = q.front();
q.pop();
//这两步是取出队首的节点
int x = tempPair.first;//横坐标
int y = tempPair.second;//纵坐标
//四种扩展情况
for(int i=0; i<4; i++)
{
int nowx = x+dx[i]; //扩展后的横坐标
int nowy = y+dy[i]; //扩展后的纵坐标
if(pd(nowx,nowy))
{
q.push({nowx,nowy});
Map[nowx][nowy]='g';
}
//符合要求执行扩展，不符合要求，忽略即可。
}
len--; //每扩展一个节点len -1
if(len==0)
{
//当len =0 时，代表当前层扩展完了，那么就代表第一个月扩展完了
k--; // 所以k--
//更新草的数目
len = q.size(); // 当前层扩展完了，那就该扩展下一层了，所以len又被赋值为下一层的节点数目的值
}
}
}
int main()
{
//输入
cin>>n>>m;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
cin>>Map[i][j];
if(Map[i][j]=='g')
{
tempPair.first=i;
tempPair.second=j;
// cout<<i<<""<<j<<endl;
q.push(tempPair);//将初始有树的结点加入队列
}
}
}
len = q.size();//记录第一层的节点数量方便后续k的计算
cin>>k;
BFS();
//输出
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
cout<<Map[i][j];
}
cout<<endl;
}
return 0;
}
例题二：走迷宫问题
输入示例：
5 5
1 0 1 1 0
1 1 0 1 1
0 1 0 1 1
1 1 1 1 1
1 0 0 0 1
1 1 5 5
输出示例：
8
解题分析：
题解代码示例：
#include <bits/stdc++.h>
using namespace std;
int vis[150][150]; //用于存储是否访问过，并且存储长度
char G[150][150]; //用于存储题目给出的地图
int n,m,ans=0;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
//上下左右移动
struct node
{
int x;
int y;
};
node Start,End;
bool pd(int x,int y)
{
if(x<1)
return 0;
//从左侧走出方格
else if(x>n)
return 0;
//从右侧走出方格
else if(y<1)
return 0;
//从上侧走出方格
else if(y>m)
return 0;
//从下侧走出方格
else if( vis[x][y]!=0)
//已经访问了
return 0;
else if(G[x][y]!='1') return 0;
//不是路不能走
else return 1;
}
bool check(int x, int y)
{
if(x == End.x&& y == End.y) //找到终点，把距离给他
{
ans = vis[x][ y];
return 1;
}
else return 0;
}
void bfs()
{
queue<node>q;
node now,next;
q.push(Start); //将起点压人队列中
vis[Start.x][Start.y] = 1;
while(!q.empty())
{
now = q.front();
if(check(now.x,now.y))
return ;
q.pop(); //将队列最前面的弹出。
for(int i=0; i<4; i++) //四个方向
{
int nextx = now.x + dx[i];
int nexty = now.y + dy[i];
if(pd(nextx,nexty)) //判断是否符合条件
{
next.x=nextx;
next.y=nexty;
q.push(next);
vis[nextx][nexty] = vis[now.x][now.y]+1; //步数+1
}
}
}
}
int main()
{
cin>>n>>m;
//memset(vis,0,sizeof(vis));
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
cin>>G[i][j];
}
}
cin>>Start.x>>Start.y>>End.x>>End.y;
ans = 0;
bfs();
cout<<ans-1<<endl;
return 0;
}
感谢您的阅读！！！
【数据结构与算法】系列文章链接: 【数据结构与算法】递推法和递归法解题（递归递推算法典型例题）
【数据结构与算法】系列文章链接: 【数据结构与算法】C++的STL模板（迭代器iterator、容器vector、队列queue、集合set、映射map）以及算法例题
