BFS(搜索)
引入
BFS(广度优先搜索)为图论中的基础算法,详见 BFS(图论) 页面。在 搜索算法 中,该算法通常指利用队列结构逐层扩展状态的搜索方式,与图论中的 BFS 算法思想一致,特别适合求解 最短路径 或 最少步骤 类问题。
解释
BFS 的核心思想是 按层扩展,从起点开始逐层扫描可到达的位置。首次遇到终点时的路径长度即为最短路径。这种方式保证了搜索的层次性与最优性。
在实际执行中,BFS 会从起点出发,先访问起点的所有直接可到达结点,这些可到达结点构成了搜索的第一层;接着,再以这些可到达结点为新的起点,依次访问它们的邻居,形成第二层;以此类推,不断向外扩展,直至找到目标结点或遍历完所有可达结点。这个过程中,算法会借助队列和访问数组,将每一层新发现的结点(访问数组中还没有记录过的)依次入队,确保同一层的结点按照访问顺序依次被处理,从而严格遵循「按层扩展」的逻辑。
BFS 非常擅于快速求解 最短路径 或 最少步骤。当算法在某一层首次遇到目标时,此时经过的路径长度(步骤数)必然是最短的。这是因为 BFS 算法的「按层扩展」机制保证了每个结点都是通过最少的步数被访问到:就像从起点出发,沿着最直接的路径不断搜索,直到抵达终点,不会出现绕路或走多余步骤的情况。在这类问题中,BFS 通常也比 DFS 的效率更高。
但是,相较于 DFS,BFS 也有其缺点。通常情况下,BFS 需要更大的内存,缺乏天然的回溯过程,且深度剪枝相对没有 DFS 灵活。
例题
例题 Luogu B3625 迷宫寻路
在一个
的迷宫矩阵中,.
表示可通行区域,#
表示障碍物。从起点
出发,每次可向上下左右四个方向移动,问是否能到达终点
。
解答
实现时需要维护一个队列来存储待处理的坐标,并配合访问标记数组避免重复计算。一个结点扩展可到达结点的时候,需要向上下左右拓展,这四个方向分别为
,
,
,
,在代码中使用了方向数组。注意判断不能拓展到有障碍物的位置。
参考实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49 | #include <iostream>
#include <queue>
using namespace std;
char a[110][110]; // 存储迷宫地图
bool vis[110][110]; // 记录访问状态
int n, m; // 迷宫尺寸
struct node {
int x, y;
}; // 定义坐标结构体
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}; // 方向数组(右左上下)
// 检查坐标是否合法
bool chk(int x, int y) {
return (x >= 1 && x <= n && y >= 1 && y <= m // 边界检查
&& !vis[x][y] // 未访问过
&& a[x][y] != '#'); // 不是障碍物
}
bool bfs() {
queue<node> q;
q.push({1, 1}); // 起点入队
vis[1][1] = 1; // 标记起点已访问
while (!q.empty()) {
node p = q.front(); // 取出队首坐标
q.pop();
int px = p.x, py = p.y;
if (px == n && py == m) return true; // 到达终点立即返回
// 向四个方向扩展
for (int i = 0; i < 4; ++i) {
int nx = px + dx[i], ny = py + dy[i];
if (chk(nx, ny)) { // 合法性检查
q.push({nx, ny}); // 新坐标入队
vis[nx][ny] = 1; // 标记已访问
}
}
}
return false;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) cin >> a[i][j];
cout << (bfs() ? "Yes" : "No") << endl;
return 0;
}
|
例题 Luogu P1135 奇怪的电梯
有
层楼和一架电梯。电梯位于第
层楼时,向上或向下移动的层数等于一个固定的数字
。如果到达的层数不合法,即不在
和
之间,相应的操作就无法进行。问:从第
楼到第
楼至少操作几次电梯?如果无法到达,输出
。
解答
本题需要计算最短路径,这正是 BFS 擅长解决的问题。实现时,需要在队列中同时维护需要处理的楼层位置和从起点
出发到达当前楼层的最短距离,并配合访问标记数组避免重复加入同一个元素。一个结点
扩展可到达结点的时候,需要向
和
扩展,注意不能到达非法楼层。当扩展到尚未到达的合法楼层时,需要将它加入队列,并记录到达该楼层的最短距离为到达当前所在楼层的最短距离加一。当首次到达结点
时,记录的最短距离就是最终答案。
代码中,直接记录距离数组,并利用距离是否为默认值(即
)来判断结点是否尚未访问。
参考实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | #include <iostream>
#include <queue>
using namespace std;
const int N = 210;
int n, a, b, k[N], d[N];
int main() {
cin >> n >> a >> b;
for (int i = 1; i <= n; ++i) cin >> k[i];
for (int i = 1; i <= n; ++i) d[i] = -1;
queue<int> q;
d[a] = 0;
q.push(a);
while (!q.empty()) {
int x = q.front();
q.pop();
if (x == b) {
break;
}
int y = x + k[x];
if (y <= n && d[y] == -1) {
d[y] = d[x] + 1;
q.push(y);
}
y = x - k[x];
if (y >= 1 && d[y] == -1) {
d[y] = d[x] + 1;
q.push(y);
}
}
cout << d[b] << endl;
return 0;
}
|
习题
本页面最近更新:2025/9/13 12:54:25,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:Ir1d, Anguei, vincent-163, c-forrest, ChungZH, Enter-tainer, ksyx, ouuan, Qlgdgasdx, TrisolarisHD, Xeonacid, ylxmf2005
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用