广度优先搜索 ,英文 Breadth-First Search,简称 BFS
广度优先搜索类似深度优先搜索,也是非常实用的算法
它从指定节点开始,逐层访问所有邻近节点,直到找到目标或遍历完所有节点。
总体流程
- 创建一个队列,把起点入队
- 遍历队首能到达的所有选项,将其入队
- 将队首元素出队
- 重复第2、3条流程,直到找到结果
代码模板:
#include<bits/stdc++.h>
using namespace std;
const int dx[] = {};
const int dy[] = {};
//定义方向,和dfs一样
int n, m;//地图的大小
struct node{
//定义队列要的信息
};//由于队列要记录很多组信息,所以要一个结构体队列
queue<node> q;
//定义一个结构体队列
bool vis[][];
//标记走过的地方
char mp[][];
//地图
void bfs(){//定义函数(其实可以直接写进主函数)
q.push(node { , , , });//把起点信息入队
while(!q.empty()){//只要还有地方没有走,就继续
node now = q.front();//把队首存下来
q.pop();//把队首出队
for(int i = 0;i < ;i++){//重复走这个点能够走到的节点
int nx = dx[i];
int ny = dy[i];
//看下一个到达的节点,同dfs
if(!vis[nx][ny] && nx > 0 && ny > 0 && nx <= n && ny <= m ……){//判断走这个点行不行
vis[nx][ny] = 1;//标记这个点走过
q.push(node { , , , });//将新的点入队
if(……){//结束条件
cout << ;//输出结果
return;
}
}
}
}
}
int main(){
//输入
bfs();
return 0;
}
以上就是简单的bfs应用