Introduction
BFS (breadth-first search) is a fundamental algorithm in graph theory; see the BFS (graph theory) page. In search algorithms, this algorithm usually refers to searching by expanding states level by level using a queue, consistent with the idea of BFS in graph theory, and is especially suitable for problems involving shortest paths or the fewest steps.
Explanation
The core idea of BFS is expansion by level: starting from the initial point, scan reachable positions level by level. The path length when the endpoint is first encountered is the shortest path. This approach guarantees the hierarchical and optimal nature of the search.
In actual execution, BFS starts from the initial point and first visits all nodes directly reachable from it. These reachable nodes form the first level of the search. Next, taking these reachable nodes as new starting points, it visits their neighbors in turn to form the second level, and so on, continually expanding outward until the target node is found or all reachable nodes have been traversed. During this process, the algorithm uses a queue and a visited array to enqueue, in order, each newly discovered node (one not yet recorded in the visited array), ensuring that nodes in the same level are processed in visitation order and thus strictly following the logic of "expansion by level".
BFS is very good at quickly solving problems involving shortest paths or the fewest steps. When the algorithm first encounters the target at a certain level, the path length (number of steps) taken at that point must be the shortest. This is because BFS's "expansion by level" mechanism ensures that every node is reached in the fewest possible steps: it searches continuously along the most direct paths from the starting point until it reaches the endpoint, without detours or extra steps. For such problems, BFS is also usually more efficient than DFS.
However, compared with DFS, BFS also has disadvantages. In general, BFS requires more memory, lacks a natural backtracking process, and offers less flexible depth pruning than DFS.
Examples
Example: Luogu B3625 Maze Pathfinding
In an maze matrix, . represents a passable area and # represents an obstacle. Starting from , one may move in each of the four directions—up, down, left, and right—at every step. Determine whether the endpoint can be reached.
Solution
During implementation, maintain a queue to store coordinates waiting to be processed, together with a visited-marker array to avoid duplicate calculations. When a node expands to reachable nodes, expand in the four directions: , , , and ; a direction array is used in the code. Be careful not to expand to positions containing obstacles.
Reference implementation
#include <iostream>
#include <queue>
using namespace std;
char a[110][110]; // stores the maze map
bool vis[110][110]; // records the visited state
int n, m; // maze dimensions
struct node {
int x, y;
}; // defines the coordinate structure
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}; // direction array (right, left, down, up)
// checks whether a coordinate is valid
bool chk(int x, int y) {
return (x >= 1 && x <= n && y >= 1 && y <= m // boundary check
&& !vis[x][y] // not visited
&& a[x][y] != '#'); // not an obstacle
}
bool bfs() {
queue<node> q;
q.push({1, 1}); // enqueue the starting point
vis[1][1] = 1; // mark the starting point as visited
while (!q.empty()) {
node p = q.front(); // remove the front coordinate
q.pop();
int px = p.x, py = p.y;
if (px == n && py == m) return true; // return immediately upon reaching the endpoint
// expand in four directions
for (int i = 0; i < 4; ++i) {
int nx = px + dx[i], ny = py + dy[i];
if (chk(nx, ny)) { // validity check
q.push({nx, ny}); // enqueue the new coordinate
vis[nx][ny] = 1; // mark as visited
}
}
}
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;
}
Example: Luogu P1135 Strange Elevator
There are floors and an elevator. When the elevator is on floor , the number of floors it moves upward or downward is a fixed number . If the destination floor is invalid, that is, not between and , the corresponding operation cannot be performed. How many elevator operations are needed at minimum to go from floor to floor ? If it is impossible to reach it, output .
Solution
This problem requires finding a shortest path, which is exactly what BFS is good at. During implementation, maintain in the queue both the floor position to process and the shortest distance from the starting floor to the current floor, together with a visited-marker array to avoid adding the same element repeatedly. When a node expands to reachable nodes, expand to and ; note that invalid floors cannot be reached. When expanding to a valid floor that has not yet been reached, add it to the queue and record its shortest distance as the shortest distance to the current floor plus one. When node is reached for the first time, its recorded shortest distance is the final answer.
In the code, the distance array is recorded directly, and whether a node has not yet been visited is determined by whether its distance has the default value (namely, ).
Reference implementation
#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;
}