一.bfs是什么
广度优先搜索（Breadth-First Search，简称BFS），是一种图遍历算法。它从给定的起始节点开始，逐层地向外扩展，先访问起始节点的相邻节点，然后再访问相邻节点的相邻节点，以此类推，直到遍历完所有可达节点。
二.基本思路
1.一直往前走，直到到达终点。
2.遇到分岔路口直接分出几条线路分开寻找。
3.遇到死路就直接把那一条路断开。
三.操作步骤
1.数据
假设一个数组a[5][5]，零代表墙，一代表路，初始点是a[1][1]，要到达a[n][n]。
假如数组为：1 0 0 1 1
1 1 1 1 0
0 0 1 1 1
0 1 1 0 1
1 1 0 0 1
2.bfs路径
从(1,1)出发，到(2,4)时分成两条线，到(3,4)时又分成两条路线，这时第一次分叉的一条路已经走到头，可以直接结束这个搜索，第二次搜索的第二条线路已经走到终点(5,5)了，可以直接结束循环。
四.代码模板
1.c++模板
// 广度优先搜索函数
// 参数:
// - start: 起始节点
// - visited: 记录是否访问过的布尔型向量
// - matrix: 表示图的二维整数向量
void bfs(int start, vector<bool>& visited, const vector<vector<int>>& matrix) {
// 创建一个队列用于广度优先搜索
queue<int> q;
// 将起始节点加入队列
q.push(start);
// 标记起始节点已访问
visited[start] = true;
// 当队列不为空时循环
while (!q.empty()) {
// 获取队列的头部节点
int u = q.front();
// 从队列中移除头部节点
q.pop();
// 输出当前访问的节点
cout << u << " ";
// 遍历当前节点的所有邻接节点
for (int v = 0; v < matrix[u].size(); ++v) {
// 如果邻接节点存在且未被访问过
if (matrix[u][v] && !visited[v]) {
// 标记邻接节点已访问
visited[v] = true;
// 将邻接节点加入队列
q.push(v);
}
}
}
}2.python模板
# 导入deque类，用于创建双端队列
from collections import deque
def bfs(graph, start):
"""
广度优先搜索算法。
通过给定的图(graph)和起始节点(start)，使用广度优先搜索策略遍历图。
参数:
- graph: 字典表示的图，键是节点，值是与该节点直接相连的节点列表。
- start: 起始节点，字符串类型。
返回值:
无返回值，直接打印遍历结果。
"""
# 初始化已访问节点集合，用于记录已经访问过的节点，避免重复访问
visited = set()
# 初始化队列，用于广度优先搜索
queue = deque([start])
# 将起始节点标记为已访问
visited.add(start)
# 当队列不为空时，继续遍历
while queue:
# 从队列左侧弹出一个节点，进行访问
vertex = queue.popleft()
# 打印访问的节点
print(vertex, end=" ")
# 遍历当前节点的所有邻接节点
for neighbour in graph[vertex]:
# 如果邻接节点未被访问过
if neighbour not in visited:
# 将邻接节点加入队列，以待后续访问
queue.append(neighbour)
# 标记该邻接节点为已访问
visited.add(neighbour)
# 示例图
graph = {
'A': ['B', 'C'],
'B': ['A', 'C', 'D'],
'C': ['A', 'B', 'D', 'E'],
'D': ['B', 'C'],
'E': ['C']
}
# 调用广度优先搜索函数，从节点'A'开始遍历图
bfs(graph, 'A')3.c模板
void bfs(int graph[MAX][MAX], int n, int start) {
int *queue = malloc(n * sizeof(int));
int front = 0, rear = 0;
int visited[MAX] = {0};
// 将起始节点入队并标记为已访问
queue[rear++] = start;
visited[start] = 1;
while (front != rear) {
int current = queue[front++];
printf("%d ", current);
// 遍历当前节点的所有邻接节点
for (int i = 0; i < n; i++) {
if (graph[current][i] && !visited[i]) {
queue[rear++] = i;
visited[i] = 1;
}
}
}
free(queue);
}
五.典型例题
1.洛谷P3395
题目传送门https://www.luogu.com.cn/problem/P3395
题目描述
B 君站在一个n×n 的棋盘上。最开始，B君站在 (1,1)(1,1) 这个点，他要走到 (n,n) 这个点。
B 君每秒可以向上下左右的某个方向移动一格，但是很不妙，C 君打算阻止 B 君的计划。
每秒结束的时刻，C 君 会在 (x,y) 上摆一个路障。B 君不能走在路障上。
B 君拿到了 C 君准备在哪些点放置路障。所以现在你需要判断，B 君能否成功走到 (n,n)。
保证数据足够弱：也就是说，无需考虑“走到某处然后被一个路障砸死”的情况，因为答案不会出现此类情况。
输入格式
首先是一个正整数 T，表示数据组数。
对于每一组数据：
第一行，一个正整数 n。
接下来 2n−2 行，每行两个正整数 x 和 y，意义是在那一秒结束后，(x,y) 将被摆上路障。
输出格式
对于每一组数据，输出 Yes 或 No，回答 B 君能否走到 (n,n)。
输入输出样例
输入 #1
2 2 1 1 2 2 5 3 3 3 2 3 1 1 2 1 3 1 4 1 5 2 2
输出 #1
Yes Yes
说明/提示
样例解释：
以下 0 表示能走，x 表示不能走，B 表示 B 君现在的位置。从左往右表示时间。
Case 1:
0 0 0 0 0 B (已经走到了)
B 0 x B x 0
Case 2:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 x 0 0 0 0 x 0 0 0 0 x 0 0
0 0 0 0 0 0 0 0 0 0 0 0 x 0 0 0 0 x 0 0
B 0 0 0 0 0 B 0 0 0 0 0 B 0 0 0 0 x B 0 ......(B君可以走到终点)
数据规模：
防止骗分，数据保证全部手造。
对于 20% 的数据，有 n≤3。
对于 60% 的数据，有 n≤500。
对于 100% 的数据，有 n≤1000。
对于 100% 的数据，有 T≤10。
参考AC代码：
#include<bits/stdc++.h>
using namespace std;
// 访问数组，用于记录每个位置的最早访问时间
int vis[2005][2005];
// 方向数组，用于表示向四个方向的移动
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
// 初始化访问数组为最大值
memset(vis,0x3f,sizeof(vis));
// 读取每个位置的访问时间
for(int i=1;i<=2*n-2;i++){
int x,y;
cin>>x>>y;
vis[x][y]=i;
}
// 使用队列进行广度优先搜索
queue<array<int,3>> q;
// 将起始位置加入队列
q.push({1,1,0});
// 标记起始位置为已访问
vis[1][1]=-1;
// 用于标记是否找到出口
int ok=0;
// 遍历队列中的元素
while(!q.empty()){
auto t=q.front();
q.pop();
// 到达出口位置
if(t[0]==n&&t[1]==n){
ok=1;
break;
}
// 尝试向四个方向移动
for(int i=0;i<4;i++){
int tx=t[0]+dx[i];
int ty=t[1]+dy[i];
// 检查新位置是否合法，并且访问时间是否更早
if(tx<1||tx>n||ty<1||ty>n||vis[tx][ty]<t[2]+1) continue;
// 标记新位置为已访问
vis[tx][ty]=-1;
// 将新位置加入队列
q.push({tx,ty,t[2]+1});
}
}
// 根据是否找到出口，输出结果
if(ok)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}2.洛谷P1332
题目传送门：https://www.luogu.com.cn/problem/P1332
题目背景
巫妖王的天灾军团终于卷土重来，血色十字军组织了一支先锋军前往诺森德大陆对抗天灾军团，以及一切沾有亡灵气息的生物。孤立于联盟和部落的血色先锋军很快就遭到了天灾军团的重重包围，现在他们将主力只好聚集了起来，以抵抗天灾军团的围剿。可怕的是，他们之中有人感染上了亡灵瘟疫，如果不设法阻止瘟疫的扩散，很快就会遭到灭顶之灾。大领主阿比迪斯已经开始调查瘟疫的源头。原来是血色先锋军的内部出现了叛徒，这个叛徒已经投靠了天灾军团，想要将整个血色先锋军全部转化为天灾军团！无需惊讶，你就是那个叛徒。在你的行踪败露之前，要尽快完成巫妖王交给你的任务。
题目描述
军团是一个 n 行 m 列的矩阵，每个单元是一个血色先锋军的成员。感染瘟疫的人，每过一个小时，就会向四周扩散瘟疫，直到所有人全部感染上瘟疫。你已经掌握了感染源的位置，任务是算出血色先锋军的领主们感染瘟疫的时间，并且将它报告给巫妖王，以便对血色先锋军进行一轮有针对性的围剿。
输入格式
第 1 行：四个整数 n，m，a，b，表示军团矩阵有 n 行 m 列。有 a 个感染源，b 为血色敢死队中领主的数量。
接下来 a 行：每行有两个整数 x，y，表示感染源在第 x 行第 y 列。
接下来 b 行：每行有两个整数 x，y，表示领主的位置在第 x 行第 y 列。
输出格式
第 1 至 b 行：每行一个整数，表示这个领主感染瘟疫的时间，输出顺序与输入顺序一致。如果某个人的位置在感染源，那么他感染瘟疫的时间为 0。
输入输出样例
输入 #1复制
5 4 2 3 1 1 5 4 3 3 5 3 2 4
输出 #1复制
3 1 3
说明/提示
输入输出样例 1 解释
如下图，标记出了所有人感染瘟疫的时间以及感染源和领主的位置。
数据规模与约定
对于 100%100% 的数据，保证 1≤n,m≤500，1≤a,b≤105。
参考AC代码：
#include<bits/stdc++.h>
using namespace std;
// 定义数组以存储输入数据
int a[250010],b[250010];
int c[250010],d[250010],sum[250010];
// 主函数，程序的入口
int main(){
// 读取测试用例参数
int n,m,x,y;
cin>>n>>m>>x>>y;
// 读取第一组数据
for(int i=1;i<=x;i++)
cin>>a[i]>>b[i];
// 读取第二组数据
for(int i=1;i<=y;i++)
cin>>c[i]>>d[i];
// 初始化sum数组为最大值，用于后续寻找最小值
memset(sum,127,sizeof(sum));
// 计算每对元素的最小距离，并更新sum数组
for(int i=1;i<=y;i++)
for(int j=1;j<=x;j++)
sum[i]=min(sum[i],abs(a[j]-c[i])+abs(b[j]-d[i]));
// 输出结果
for(int i=1;i<=y;i++)
cout<<sum[i]<<endl;
return 0;
}3.洛谷P7243
题目传送门：最大公约数 - 洛谷
题目背景
“寻求最大公约数是人民民主的真谛。……”
初秋，从枝丫滴下的阳光，柔和，在教室的窗棱溅起，润湿晨读的少女的脸颊。
“阿绫，阿绫”，天依低俯身子，八字辫耷拉在竖起的课本沿，“我们的最大公约数是多少呢？”
“一定不小吧”，左手悄悄捏捏天依的小臂，“比如呀，有一个公因子，叫做‘你喜欢我，我也喜欢你’。”
题目描述
相反，人际圈形形色色，公约数小得可怜，似乎很难保持自己的个性因而变成无趣的人呢。
现在把人际抽象成一个 n×m 的矩形，每个人初始的个性为 ai,j。从第二天开始，每个人会与上下左右四个人（如果存在）建立人际关系，其个性变为昨天自己和四周人个性的最大公约数。那么对于第 x 行第 y 列的人，在多少天后他的个性会变为 11 呢？
简化题意
有一个 n×m 的矩阵 a。对一个矩阵进行变换，定义为将这个矩阵内的所有元素变为其上下左右四个元素（不存在则忽略）及自身的最大公约数。询问 ax,y 在进行最少多少次变换之后会变成 1。如果可以使ax,y 经过若干次变换变成 11，输出其中最小的次数；否则输出 −1。
输入格式
第一行两个整数 n,m，表示矩阵的行数和列数。
接下来 n 行，每行 m 个整数，第 i 行第 j 列的整数 ai,j 描述了该位置的人的初始个性。
接下来一行两个整数x,y，表示某个指定的人的位置。
输出格式
一行一个整数 d，表示第 x 行第 y 列的人的个性会在 d 天后变为 1；特别地，若永远不会变为 1，应输出 −1。
输入输出样例
输入 #1复制
2 2 2 2 1 2 2 1
输出 #1复制
0
输入 #2复制
2 2 2 2 2 2 1 1
输出 #2复制
-1
输入 #3复制
3 3 3 2 3 2 3 2 3 2 3 2 2
输出 #3复制
1
说明/提示
样例解释 3
第一天的个性矩阵（也就是最开始的矩阵）为
(323232323)⎝⎛323232323⎠⎞
第二天的个性矩阵为
(111111111)⎝⎛111111111⎠⎞
可见只需要经过一天，a2,2 就会变为 1，所以答案为 1。
数据规模与约定
本题采用捆绑测试。
对于 100%100% 的数据，1≤n,m≤2×103，1≤ai,j≤1018，1≤x≤n，1≤y≤m。
| 子任务 | 分值 | n,m | 特殊限制 |
|---|---|---|---|
| 1 | 1 | / | 保证给出的位置个性永远不会变为 1 |
| 2 | 1 | / | 保证 x,y=1 |
| 3 | 3 | ≤2 | / |
| 4 | 10 | ≤102 | / |
| 5 | 30 | ≤5×102 | / |
| 6 | 10 | / | 保证对于所有的 ai,j≤2 |
| 7 | 10 | / | 保证 x 与 y 都等于 1 |
| 8 | 35 | / | / |
参考AC代码：
#include<bits/stdc++.h>
using namespace std;
// 定义常量N，用于数组大小，足以覆盖所有可能的输入值
const int N=2e3+10;
// a数组存储输入的矩阵元素，s数组用于存储从(x, y)到其他点的距离上的最大公约数
long long a[N][N],s[N];
/**
* 计算两个长整型数的最大公约数
* @param a 第一个长整型数
* @param b 第二个长整型数
* @return a和b的最大公约数
*/
long long gcd(long long a,long long b){
long long x=0;
while((x=a%b)){
a=b;
b=x;
}
return b;
}
int main(){
int n,m,x,y;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
cin>>x>>y;
// 如果(x, y)处的元素为1，则输出0并结束程序
if(a[x][y]==1){
cout<<0<<endl;
return 0;
}
for(int i=0;i<=n+m;i++)
s[i]=a[x][y];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(i!=x||j!=y){
int z=abs(x-i)+abs(y-j);
s[z]=gcd(a[i][j],s[z]);
}
for(int i=1;i<=n+m;i++){
s[i]=gcd(s[i-1],s[i]);
if(s[i]==1){
cout<<i<<endl;
return 0;
}
}
cout<<-1<<endl;
return 0;
}