2024-12-28-深度搜索DFS和广度搜索BFS
深度搜索(DFS)和广度搜索(BFS)
深度搜索(DFS)
一、搜索方法：
沿出发顶点的第一条路径尽量深入，遍历路径上所有顶点；然后退回到该顶点，搜索其它路径，直到以该顶点为始点的所有路径的顶点都被访问，深度搜索算法是递归算法，因为对于没一个节点来说，执行的是同样的操作。
简单来说，深度搜素算法就是一条道走到黑，走不动了再回溯回去，选择其他路径，举个例子，对于下面的图，假设从1开始遍历：
（1）第一步，访问结点1并标记
int dxy[4][2]={//模拟上下左右四个方向
-1,0,//向上（x减一，y不变）
1, 0,//向下
0,-1,//向左
0, 1//向右
}
void dfs(int x0,int y0,int x1,int y1)
{
//(x0,y0)是出发点，(x1,y1)是目标点
if(x0==x1&&y0==y1)//找到目标点
{
//执行操作如输出路径等
return；
}
for(int i=0;i<4;i++)//遍历四个方向每一个分支，对每一个分支都进行深度搜索
{
int dx=dxy[i][0];//移动后的横坐标
int dy=dxy[i][1];//移动后的纵坐标
if(坐标越界||遇到障碍物||...)//不满足条件
continue;
//执行操作
dfs(dx,dy,x1,y1)//深度遍历
//遍历结束恢复操作
}
}广度搜索（BFS）
一、搜索方法
广度搜索，顾名思义，就是更大范围内搜索，与深度搜索不同的是，深度搜索是一次搜索一条路径，一直搜索到走不通为止；而广度搜索是同时搜索所有路径，相当于一层一层地搜索，就好比波浪的扩展一样。此搜索方法跟树的层次遍历类似，因此宽度搜索一般都用队列存储结构。搜索原则：
（1）访问遍历出发顶点，该顶点入队
（2）队列不空，则队头顶点出队；
（3）访问出队顶点所有的未访问邻接点并将其入队；
（4）重复（2）（3），直到队空或者找到目标点
举个例子，还是对下面这个图进行广度遍历：
二、用途
虽然看似广度搜索一次扩张了很多个点，但实际上任然是一个结点一个结点地搜索，只是它是以层层扩张的方式进行搜索。广度搜索也常用于解决图的遍历，在求一个点到另一个点的最短距离时，广度搜索比深度搜索更有优势，因为广度搜索是层层遍历的，所以一定存在某条路径最先到达目标点，只要找到目标点后就退出，就不用搜索所有点。
广度搜索也是分支限界法的主要算法（当然，分支限界也可能是广度搜索和宽度搜索的结合）。广度搜索最常解决的问题类型是：求从某一个状态到另一个状态的最小步数，每一个状态对应多个（扩展结点个数）不同的操作。
三、算法模板
#include<iostream>
#include<queue>
using namespace std;
struct state
{
int a,b;//存储相应信息
int step;//存储当前结点的步数
};
queue<state>Q;
int bfs(int a,int b,int A,int B)//返回最小步数
{
//参数a,b是初始状态，
//参数A,B是目标状态判断条件；
while(!Q.empty())Q.pop();//清空队列
state P;
P.a=a;P.b=b;P.step=0;//初始结点
Q.push(P);//初始结点入队
while(!Q.empty())//队列非空
{
state head=Q.front();//保存队头
Q.pop();//队头出队
//以下扩展每个结点的邻接结点*************************
state p=head;
p.a=...//执行操作
p.b=...//执行操作
p.step++;//步数加一
//判断p.a,p.b是否合法（剪枝处理）
if(ok(p.a,p.b))
{
if(p.a==A&&p.b==B)//判断该状态是否满足目标状态
return p.step;//返回步数
Q.push(p);//否则入队
}
//扩展其他结点
......
//扩展结点结束*************************************
}
return -1;//不能到达目标状态，返回-1;
}经典例题
68747470733a2f2f:626c6f672e6373646e2e6e65742f71715f3432373132333531:2f61727469636c652f64657461696c732f3936333633363931