在图论中，广度优先遍历（Breadth-First Search，BFS）是一种图遍历算法，它以一种逐层的方式探索图的节点。通过从起始节点开始，逐层向外扩展，BFS能够帮助我们解决许多与图相关的问题。
算法步骤
广度优先遍历的算法步骤如下：
选择起始节点： 选择图中的一个节点作为遍历的起点。将该节点标记为已访问。
创建队列： 创建一个队列（可以使用数组模拟），并将起始节点加入队列。
循环遍历： 进入循环，直到队列为空为止。
从队列中取出一个节点，记为当前节点。
访问当前节点，并处理与当前节点相邻的尚未访问过的节点。
将这些尚未访问过的相邻节点加入队列，并标记为已访问。
继续遍历： 重复步骤 3，直到队列为空。这样保证了图中所有可达节点都会被访问到。
应用示例：迷宫最短路径问题
考虑以下问题：有一个迷宫，由多个单元格组成，有些单元格是墙壁，有些是可以通行的。我们的目标是找到从起始位置到达目标位置的最短路径，只能沿上、下、左、右四个方向移动，不能穿越墙壁。这个问题可以使用广度优先遍历来解决。
这里笔者自己搭建了一个迷宫，其中"S"表示起始位置，"E"表示目标位置，"."表示可以通行的空地，"#"表示墙壁。
S . . # . . .
. # . . . # .
. # # # . . .
. . . . # # E
我们可以将迷宫表示为一个二维网格，其中每个单元格都是一个节点。通过BFS，我们可以从起始位置开始，逐层向外扩展，直到找到目标位置为止。在扩展的过程中，我们需要注意避开墙壁，同时记录经过的步数，这样在找到目标位置时就能得到最短路径的步数。
#include <iostream>
#include <queue>
using namespace std;
const int ROWS = 4;
const int COLS = 7;
const char grid[ROWS][COLS] = {
{'S', '.', '.', '#', '.', '.', '.'},
{'.', '#', '.', '.', '.', '#', '.'},
{'.', '#', '#', '#', '.', '.', '.'},
{'.', '.', '.', '.', '#', '#', 'E'}
};
int dr[] = {-1, 1, 0, 0}; // 上、下、左、右
int dc[] = {0, 0, -1, 1};
bool isValid(int r, int c) {
return r >= 0 && r < ROWS && c >= 0 && c < COLS && grid[r][c] != '#';
}
int BFS(int startR, int startC, int endR, int endC) {
queue<pair<int, int>> q;
q.push({startR, startC});
vector<vector<bool>> visited(ROWS, vector<bool>(COLS, false));
visited[startR][startC] = true;
int steps = 0;
while (!q.empty()) {
int levelSize = q.size();
for (int i = 0; i < levelSize; ++i) {
int r = q.front().first;
int c = q.front().second;
q.pop();
if (r == endR && c == endC) {
return steps;
}
for (int j = 0; j < 4; ++j) {
int nr = r + dr[j];
int nc = c + dc[j];
if (isValid(nr, nc) && !visited[nr][nc]) {
q.push({nr, nc});
visited[nr][nc] = true;
}
}
}
steps++;
}
return -1; // 无法到达目标位置
}
int main() {
int startR = 0, startC = 0;
int endR = 3, endC = 6;
int shortestPath = BFS(startR, startC, endR, endC);
if (shortestPath != -1) {
cout << "Shortest path from S to E: " << shortestPath << " steps" << endl;
} else {
cout << "Cannot reach the target position" << endl;
}
return 0;
}
