Breadth-First Search (BFS)

03 Nov 2024

1. Introduction

Breadth-First Search (BFS) explores states in order of their distance from a starting point. It first visits positions one step away, then positions two steps away, and continues outward layer by layer.

Unlike DFS, which follows one path as far as possible before returning, BFS processes every state at the current distance before moving to the next distance. Therefore, in a graph or grid where every move has the same cost, the first time BFS reaches a position, it has found the shortest distance from the start to that position.

BFS uses a queue to store positions waiting to be explored. The earliest discovered position is removed from the front, while newly discovered positions are added to the back. This first-in, first-out order keeps the search organized by layers.

2. Basic Idea

For a grid, BFS follows this process:

Put the starting cell into the queue and set its distance to 0.
Remove the front cell and examine its four neighbors: up, down, left, and right.
If a neighbor is inside the grid, passable, and unvisited, set its distance to the current distance plus 1 and add it to the back of the queue.
When the queue is empty, every position reachable from the start has been explored.

The array dist can record both distance and visit status. Initialize every value to -1, meaning unvisited. Once a non-negative distance is written, that cell has already entered the queue and does not need to be added again.

3. Example: Shortest Path in a Maze

Given a grid, S is the start, T is the target, # is a wall, and every other cell is passable. You may move one cell up, down, left, or right at a time. Find the minimum number of steps from S to T.

Because every move costs 1, BFS can solve the problem directly. The distance assigned when the target is first visited is the shortest number of steps. If dist[tx][ty] remains -1 after the search, the target cannot be reached.

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int n, m;
char grid[N][N];
int dist[N][N];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int main() {
    cin >> n >> m;

    int sx, sy, tx, ty;
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 'S') sx = i, sy = j;
            if (grid[i][j] == 'T') tx = i, ty = j;
        }
    }

    memset(dist, -1, sizeof dist);
    queue<pair<int, int> > q;
    dist[sx][sy] = 0;
    q.push({sx, sy});

    while (!q.empty()) {
        auto current = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = current.first + dx[i];
            int ny = current.second + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (grid[nx][ny] == '#') continue;
            if (dist[nx][ny] != -1) continue;

            dist[nx][ny] = dist[current.first][current.second] + 1;
            q.push({nx, ny});
        }
    }

    cout << dist[tx][ty];
    return 0;
}

For example, the shortest route from S to T in the following 3 by 4 grid has length 5:

S...
##.#
...T

Every passable cell enters and leaves the queue at most once, and its four directions are checked once. The time complexity is therefore O(nm), where n and m are the number of rows and columns.

The key idea of BFS is to search layer by layer. When a problem asks for the minimum number of operations, the shortest number of steps, or the nearest distance and every move has the same cost, consider treating each state as a node in a queue and expanding outward from the start with BFS.

Breadth-First Search (BFS)

Related Posts