Skip to content

BFS (Search)

Introduction

BFS (Breadth-First Search) is a fundamental algorithm in graph theory. For details, see the BFS (Graph Theory) page. In the context of search algorithms, it usually refers to a search method that expands states layer by layer using a queue structure. Its idea is consistent with the BFS algorithm in graph theory and is particularly suitable for solving shortest path or minimum steps problems.

Explanation

The core idea of BFS is layer-by-layer expansion, scanning reachable positions from the starting point layer by layer. The path length when the target is first encountered is the shortest path. This approach ensures the hierarchical nature and optimality of the search.

In practice, BFS starts from the initial point, first visiting all directly reachable nodes from the start, which constitute the first layer of the search. Then, using these reachable nodes as new starting points, it visits their neighbors to form the second layer, and so on, continuously expanding outward until the target node is found or all reachable nodes are traversed. During this process, the algorithm uses a queue and a visited array to enqueue newly discovered nodes (those not yet recorded in the visited array) layer by layer, ensuring that nodes in the same layer are processed in the order they are visited, thus strictly adhering to the "layer-by-layer expansion" logic.

BFS is particularly adept at quickly solving shortest path or minimum steps problems. When the algorithm first encounters the target at a certain layer, the path length (number of steps) taken at that moment is necessarily the shortest. This is because the "layer-by-layer expansion" mechanism of BFS ensures that each node is visited with the minimum number of steps: starting from the initial point, the search proceeds along the most direct path until reaching the target, without detours or unnecessary steps. For such problems, BFS is usually more efficient than DFS.

However, compared to DFS, BFS also has its drawbacks. Typically, BFS requires more memory, lacks a natural backtracking process, and is less flexible in depth pruning than DFS.

Examples

Example Luogu B3625 Maze Pathfinding

In an \(n \times m\) maze matrix, . represents passable areas, and # represents obstacles. Starting from \((1,1)\), you can move up, down, left, or right each time. Determine whether you can reach the endpoint \((n,m)\).

Solution

During implementation, maintain a queue to store coordinates to be processed, along with a visited array to avoid repeated calculations. When expanding from a node to reachable nodes, you need to expand in four directions: up, down, left, and right, corresponding to \((x, y + 1)\), \((x, y - 1)\), \((x + 1, y)\), and \((x - 1, y)\). In the code, a direction array is used. Note that you cannot expand to positions with obstacles.

Reference Implementation 
 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];    // Store the maze map
bool vis[110][110];  // Record visited status
int n, m;            // Maze dimensions

struct node {
  int x, y;
};  // Define coordinate structure

int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};  // Direction arrays (right, left, down, up)

// Check if coordinates are 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 starting point
  vis[1][1] = 1;   // Mark starting point as visited
  while (!q.empty()) {
    node p = q.front();  // Get front coordinate from queue
    q.pop();
    int px = p.x, py = p.y;
    if (px == n && py == m) return true;  // Return immediately upon reaching the destination
    // 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 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 \(n\) floors and an elevator. When the elevator is on floor \(i\), the number of floors it moves up or down equals a fixed number \(k_i\). If the target floor is invalid (i.e., not between \(1\) and \(n\)), the corresponding operation cannot be performed. Question: What is the minimum number of elevator operations required to go from floor \(a\) to floor \(b\)? If unreachable, output \(-1\).

Solution

This problem requires computing the shortest path, which is exactly what BFS excels at. During implementation, the queue should store both the floor position to be processed and the shortest distance from the starting floor \(a\) to the current floor, along with a visited array to avoid adding the same element repeatedly. When expanding from a node \(i\) to reachable nodes, you need to expand to \(i + k_i\) and \(i - k_i\), ensuring not to reach invalid floors. When expanding to a valid floor that has not been visited, add it to the queue and record the shortest distance to that floor as the shortest distance to the current floor plus one. When node \(b\) is first reached, the recorded shortest distance is the final answer.

In the code, the distance array is directly recorded, and whether a node has been visited is determined by checking if the distance is the default value (i.e., \(-1\)).

Reference Implementation 
 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;
}

Exercises

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用