前言
BFS（Breadth First Search，广度优先搜索）：其思路为从起点开始一层一层扩散式搜索，直至全部搜索完成。所以所得到的解为步骤最少的解。（建议与DFS共同阅读）
实现思路（建议用简单数据手写模拟运行或者看看下面例题的代码）：
1.将起点放入队列并标记为已搜索
- 【循环条件及开始】 判断队列是否为空（为空则结束循环，否则继续进行）
3.将与队首结点相邻且未搜索过的所有结点加入队列并标记为已搜索
4.队首结点弹出 【循环结束】
咳咳：DFS用栈（递归），BFS用队列
简单介绍后根据思路尝试一道水题吧
题目链接：洛谷P1443 马的遍历
题目描述
有一个n×m 的棋盘，在某个点 (x, y)上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
输入格式
输入只有一行四个整数，分别为 n, m, x, y。
输出格式
一个 n×m 的矩阵，代表马到达某个点最少要走几步（左对齐，宽 5 格，不能到达则输出 −1）。
输入输出样例
输入
3 3 1 1
输出
0 3 2
3 -1 1
2 1 4
ac代码
//时间：44ms(O2:38ms) 内存：856.00KB
#include <bits/stdc++.h>
using namespace std;
#define MAXN 405
int n,m,x,y;
int a[MAXN][MAXN]; //棋盘也是记录答案
int nextx[8]={-2,-1,1,2,2,1,-1,-2}; //nextx和nexty组成下一步
int nexty[8]={1,2,2,1,-1,-2,-2,-1};
queue<pair<int,int> > q; //结点队列
int main()
{
int step=0,i,j;
cin>>n>>m>>x>>y; //按题意输入
for(i=1;i<=n;i++) //初始化棋盘，为-1则为未搜索过
for(j=1;j<=m;j++)
a[i][j]=-1;
q.push(make_pair(x,y)); //起点入队
a[x][y]=0; //起点最少0步到达
//BFS
while(!q.empty()){ //只要还有能搜索的
int nx,ny,tx,ty;
tx=q.front().first; //tx，ty记录当前结点坐标
ty=q.front().second;
for(i=0;i<8;i++){ //朝八个方向搜索
nx=tx+nextx[i]; //nx,ny为下一bu
ny=ty+nexty[i];
//如果越界或者已经访问过则跳过
if(nx<1||nx>n||ny<1||ny>m||a[nx][ny]!=-1) continue;
a[nx][ny]=a[tx][ty]+1; //否则代表第一次访问到该结点，故其最少步骤为当前结点最少步骤加一
q.push(make_pair(nx,ny)); //该结点入队
}
q.pop(); //头节点出队
}
for(i=1;i<=n;i++){ //按题意输出
for(j=1;j<=m;j++){
printf("%-5d",a[i][j]);
}
cout<<endl;
}
return 0;
}
练习
洛谷P1144 最短路计数
最短路计数
题目描述
给出一个 N 个顶点 M 条边的无向无权图，顶点编号为 $1\sim N$。问从顶点 1 开始，到其他每个点的最短路有几条。
输入格式
第一行包含 2 个正整数 N,M，为图的顶点数与边数。
接下来 M 行，每行 2 个正整数 x,y，表示有一条由顶点 x 连向顶点 y 的边，请注意可能有自环与重边。输出格式
共 N 行，每行一个非负整数，第 i 行输出从顶点 1 到顶点 i 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 ans mod 100003 后的结果即可。如果无法到达顶点 i 则输出 0。
样例 #1
样例输入 #1
5 7 1 2 1 3 2 4 3 4 2 3 4 5 4 5样例输出 #1
1 1 1 2 4提示
1 到 5 的最短路有 4 条，分别为 2 条 $1\to 2\to 4\to 5$ 和 $2$ 条 $1\to 3\to 4\to 5$（由于 $4\to 5$ 的边有 $2$ 条）。
对于 20% 的数据，$1\le N \le 100$；
对于 60% 的数据，$1\le N \le 10^3$；
对于 100% 的数据，$1\le N\le10^6$，$1\le M\le 2\times 10^6$。
解题思路
该题要求有多少条不同的最短路，而且边无权（长度相等），那么用BFS，初次找到即为最短距离。
所以对于初次搜索到的结点，将其标记入队，得到其最短距离为 其上一个点的最短距离+1，最短路径的条数+=上一结点的条数。
如果搜到了搜过的结点并且当前节点的距离+1等于其最短距离,那么其最短路径条数+=当前结点的条数。
ac代码
//时间：442ms(O2:181ms) 内存 :35.68MB
#include <bits/stdc++.h>
using namespace std;
int n,m,s;
int dis[1000005],ans[1000005]; //dis记录距离,ans记录多少条最短路
int book[1000005]; //标记点是否搜索过
vector<int> a[1000005]; //邻接表存储图
queue<int> q;
int u,v,w;
const int INF=(1<<31)-1; //无法到达点的距离
const int MD=100003;
int main()
{
cin>>n>>m;
int i,j,tmin;
for(i=1;i<=m;i++){ //按题意输入，邻接表存储
scanf("%d%d",&u,&v);
a[u].push_back(v); //无向边
a[v].push_back(u);
}
for(i=1;i<=n;i++){ //初始化
dis[i]=INF;
}
memset(book,0,sizeof(book));//初始化标记
int s=1;
book[s]=1; //标记起点，距离为0 ，最短路条数一条
dis[s]=0;
ans[s]=1;
q.push(s); //起点入队
//核心代码
while(!q.empty()){
int t=q.front();
for(i=0;i<a[t].size();i++){ //遍历可以抵达的点
if(book[a[t][i]]==0){ //为搜索过
book[a[t][i]]=1;
ans[a[t][i]]+=ans[t];
ans[a[t][i]]%=MD;
dis[a[t][i]]=dis[t]+1; //记录最短距离
q.push(a[t][i]); //该点入队
}else if(dis[a[t][i]]==dis[t]+1){//搜索过但是从t点抵达也是最短路径
ans[a[t][i]]+=ans[t];
ans[a[t][i]]%=MD;
}
}
q.pop();
}
//输出
for(i=1;i<=n;i++){
printf("%d\n",ans[i]);
}
return 0;
}
力扣练习
力扣1129. 颜色交替的最短路径
在一个有向图中，节点分别标记为 0, 1, ..., n-1。图中每条边为红色或者蓝色，且存在自环或平行边。
red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。类似地，blue_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的蓝色有向边。
返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 answer[x] = -1。
示例 1：
输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
输出：[0,1,-1]
示例 2：
输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
输出：[0,1,-1]
示例 3：
输入：n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
输出：[0,-1,-1]
示例 4：
输入：n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
输出：[0,1,2]
示例 5：
输入：n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
输出：[0,1,1]
提示：
1 <= n <= 100
red_edges.length <= 400
blue_edges.length <= 400
red_edges[i].length == blue_edges[i].length == 2
0 <= red_edges[i][j], blue_edges[i][j] < n