#创作计划#广度优先搜索的实现（原创）
2024-01-27 20:59:13
发布于：浙江
概述：
广度优先搜索（也称宽度优先搜索，缩写BFS）是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始，辐射状地（就和MC中的水一个样）遍历其周围较广的区域，故得名。
广搜是一种用于图形搜索和遍历的算法，它从起始节点开始，依次访问其相邻节点，然后再依次访问这些节点的相邻节点，以此类推，直到找到目标节点或者遍历了整个图形。
模板：
1. 定义一个节点数据结构
struct node{
int x, y, step;
};
其中x、y记录当前节点的位置，step记录步数。
2. 定义地图数组、标记数组和方向数组。
int maze[<行数>][<列数>];
bool visited[<行数>][<列数>];
int arr[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
P. S：方向数组视情况而定，有时情况更加复杂
3.BFS函数
过程：
- 将起始节点标记为已访问，并将其加入到队列中。
- 当队列不为空时，从队列的头部取出一个节点，依次访问它的相邻节点。
- 如果相邻节点未被访问，则将其标记为已访问，并将其加入到队列的尾部。
- 重复步骤2和步骤3，直到队列为空或者找到目标节点。
int bfs(地图大小, 起点, 终点)
{
初始化队列;
起点入队，标记走过;
while(队列不为空)
{
if(到达终点)
{
打印结果;
return;
}
for(枚举队首能通达的所有节点)
{
if(条件成立)
{
节点入队;
标记;
}
}
}
}
标程：
输入：第1行输入地图的行数n和列数m，第2行输入起点坐标(sx, sy)，第3行终点坐标(ex, ey)，此后的n行输入一个地图（.表示通道，#表示墙）
输出：从起点到终点的最少步数，若无法到达则输出
数据范围： 且 且
样例输入：
5 5
1 1
4 5
.....
#.###
#...#
#..#.
##...
样例输出：
9
这是一道最短路径的模板题，许多题目的代码和这道题基本完全一样，不过是换了一种表述。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
struct node
{
int x, y, step;
};
int maze[501][501];
bool visited[501][501];
int arr[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int BFS(int n, int m, int sx, int sy, int ex, int ey)
{
queue<node> q;
q.push(node{sx, sy, 0}); //将起始节点加入到队列中
visited[sx][sy] = 1; //将起始节点标记为已访问
while (!q.empty()) //当队列不为空时
{
node now = q.front(); //从队列的头部取出一个节点
q.pop();
if (now.x == ex && now.y == ey) //找到目标节点，返回步数
return now.step;
for (int i = 0; i < 4; ++i) //访问它的相邻节点
{
int x = now.x + arr[i][0];
int y = now.y + arr[i][1];
if (x >= 1 && x <= n && y >= 1 && y <= m && !visited[x][y] && !maze[x][y])
//判断此节点是否在地图范围内，是否未被访问，是否不为墙
{
visited[x][y] = 1; //将此节点标记为已访问
q.push(node{x, y, now.step + 1}); //将此节点加入到队列的尾部
}
}
}
return -1;
}
int main()
{
int n, m, sx, sy, ex, ey;
cin >> n >> m >> sx >> sy >> ex >> ey;
char x;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
cin >> x;
if (x == '.')
maze[i][j] = 0;
else
maze[i][j] = 1;
}
cout << BFS(n, m, sx, sy, ex, ey);
return 0;
}
图中的BFS（例题为树上两点之间的距离，来自信友队）：
题目描述：
给你一棵无根树，求树上两个点之间的距离。
输入格式：
第一行输入一个整数 n，表示树的总点数。
()
接下来n−1行每行输入两个整数表示一条树边
最后一行输入两个点 a,b
输出格式：
输出一个整数表示 a,b之间的距离
样例输入：
4
1 2
2 3
3 4
1 4
样例输出：
3
标程：
#include <bits/stdc++.h>
using namespace std;
struct node
{
int x, step;
};
vector<int> v[1001];
int vis[1001];
int n, a, b;
int BFS()
{
queue<node> q;
q.push(node{a, 0});
vis[a] = 1;
while (!q.empty())
{
node now = q.front();
q.pop();
if (now.x == b)
return now.step;
for (int i = 0; i < v[now.x].size(); i++)
{
if (vis[v[now.x][i]] == 0)
{
vis[v[now.x][i]] = 1;
q.push(node{v[now.x][i], now.step + 1});
}
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n - 1; i++)
{
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
cin >> a >> b;
vis[a] = 1;
cout << BFS();
return 0;
}
这道题说白了就是图的BFS，只得注意的是本标程中图的存储方式是邻接表，即使用n个向量（vector[ ]）实现，每一个向量存对应顶点的所有相连的点（邻居）。
既然提都提到了，那么就把无权值无向图的邻接表的标程放出来吧：
for (i = 1; i <= m; i++) // m条边(无权值)
{
cin >> u >> v; // 读入两个顶点序号
g[u].push_back(v);
g[v].push_back(u); // 无向图的对称性,如果是有向图则不要有这句！
}
结语：
DFS和BFS同为最最最基础的搜索算法，是参加比赛必须掌握的，最主要的还是——
刷题！
刷题！！
刷题！！！
刷题！！！！
刷题！！！！！
刷题！！！！！！
与其在这儿补干货，还不如在课上好好听，课后多刷题（doge
——MajmDZB
全部评论 10
dan 是，的确有点不好，那个方向数组可以讲清楚点，我是这么写的，比较清楚
int dx[4]={0,0,-1,1};//上下左右
int dy[4]={1,-1,0,0};//上下左右2024-05-05 来自 广东
1https://www.acgo.cn/contest/1274/detail?matchRoundId=1274&examId=34860&openLevel=2&teamCode=1703714507764441088这个玩意
2024-01-28 来自 浙江
0
有帮助，赞一个