搜索分为深度优先搜索（dfs）和广度优先搜索（bfs）
深度搜索和广度搜索的区别是：
深度搜索是往深度方向进行搜索的，先选一条路走到底，再选另一条路；
广度搜索是一层一层的，把一层上的所有情况都搜索到了，才向下一层搜索。
一般情况下，深度优先搜索法占内存少但速度较慢，广度优先搜索算法占内存多但速度较快，在距离和深度成正比的情况下能较快地求出最优解。
目录
深度优先搜索
经典例子——解救小哈（深度搜索）
广度优先搜索
经典例子——解救小哈（广度搜索）
先学习深度优先搜索。
深度优先搜索
经典例子——解救小哈（深度搜索）
【题目描述】
有一天，小哈一个人去玩迷宫。但是方向感很不好的小哈很快就迷路了。小哼得知后便要去解救无助的小哈。小哼当然是有备而来，已经弄清楚了迷宫的地图，现在小哼要以最快的速度去解救小哈。问题就此开始了……
迷宫由n行m列的单元格组成（n和m都小于等于50），每个单元格要么是空地（用0表示），要么是障碍物（用1表示）。你的任务是帮助小哼找到一条从迷宫的起点(x,y)通往小哈所在位置（q,p)的最短路径。注意障碍物是不能走的，当然小哼也不能走到迷宫之外。
【输入】
首先输入n和m，代表二维数组（迷宫）的行和列。
接着输入一个二维数组。
最后输入迷宫的起点坐标（x,y)和小哈所在的位置（q，p）。
【输出】
小哼从起点通往小哈位置的最短路径。
样例输入
5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3
样例输出
7
解题思路
在每一块空地上，可以往四个方向去尝试，但是要避免出界，还要避开障碍物，当一个地方走不通时再回到这里，去尝试另外一个方向。
可以定义一个数组存储方向。当小哼到达一个可以到达的位置，要判断小哼是否到达小哈的位置，如果没有就接着找下一个位置，因为题目要找最短路径，所以要定义一个变量记录前面走过步数的最小值。
代码如下：文章来源地址https://www.toymoban.com/news/detail-415533.html
#include<stdio.h>
int n,m,q,p,min=999999;
int a[51][51];
int book[51][51];
//标记一次路径中走过的点，避免重复经过
void dfs(int x,int y,int step)
{
int next[4][2]={0,1,0,-1,1,0,-1,0};
//分别表示向右走，向左走，向下走，向上走
int tx,ty,i;
for(i=0;i<4;i++)
{
if(x==q&&y==p)
{
if(step<min)
min=step;
return ;
}
tx=x+next[i][0];
ty=y+next[i][1];
if(tx<1||tx>n||ty<1||ty>m)
continue;
if(book[tx][ty]==0&&a[tx][ty]==0)
{
book[tx][ty]=1;
//标记已经走过
dfs(tx,ty,step+1);
book[tx][ty]=0;
//一次进行到底后要把标记取消
}
}
return ;
}
int main()
{
int i,j,x,y;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
}
scanf("%d %d %d %d",&x,&y,&q,&p);
book[x][y]=1;
//第一个点要标记
dfs(x,y,0);
//从起点开始，步数为0
printf("%d\n",min);
return 0;
}广度优先搜索
经典例子——解救小哈（广度搜索）
接着上面的例子，我们把深度搜索改为广度搜索。
解题思路
需要用到结构体和队列。
假设小哼在起点（1,1）处（记得要标记起点，防止重复经过），那么下一步可以到达（1,2）或（2,1），（1,2）和（2,1）这两个点为新拓展的点。 但是小哈并不在（1,1），（1,2）这两个点上，记得把这两点标记。如图：
然后进行第二步可以走的点都走到，有（2,2）和（3,1），把他们标记。如图：
接着第三步，这一层可以到达（2,3），（3,2），（4，1）把他们标记。如图：
此时也没有到达小哈所在的位置，接着重复上述操作，直至到达终点。文章来源：https://www.toymoban.com/news/detail-415533.html
代码如下：
#include<stdio.h>
int a[51][51],book[51][51];
//储存迷宫，标记已经走过的点
struct queue
{
int x;
int y;
int step;//记录当前走的步数
};
int main()
{
struct queue k[2510];
//队列不会超过50*50
int next[4][2]={0,1,0,-1,1,0,-1,0};
//分别表示向下走，向上走，向左走，向右走
int i,j,n,m,x0,y0,q,p;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
}
scanf("%d %d %d %d",&x0,&y0,&q,&p);
int flag=0;
//用来标记是否到达终点，然后结束循环
int head=1,tail=1,tx,ty;
//将队列初始化
k[tail].x=x0;
k[tail].y=y0;
k[tail].step=0;
book[x0][y0]=0;
tail++;
while(head<tail)
//循环进行时，队列不能为空
{
for(i=0;i<4;i++)
{
tx=k[head].x+next[i][0];
ty=k[head].y+next[i][1];
if(tx<1||tx>n||ty<1||ty>m)//不能越界
continue;
if(a[tx][ty]==0&&book[tx][ty]==0)
{
book[tx][ty]=1;
k[tail].x=tx;
k[tail].y=ty;
k[tail].step=k[head].step+1;
tail++;
}
if(tx==q&&ty==p)
{
flag=1;
break;
}
}
if(flag==1)
break;
head++;
}
printf("%d\n",k[tail-1].step);
//因为我们要打印到终点这一步的步数
//但是这里的tail是指向队尾的下一个位置，所以记得要-1
return 0;
} 到了这里，关于万能的搜索——深度搜索和广度搜索的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
