Breadth-First Search

Spreading outward

Breadth-first search visits everything one step away, then everything two steps away, and so on. It uses a queue rather than recursion, which is what makes it spread sideways instead of diving deep.

static int[] bfs(int start, List<List<Integer>> adj, int n) {
    int[] distance = new int[n];
    Arrays.fill(distance, -1);           // -1 means not reached yet

    Queue<Integer> queue = new ArrayDeque<>();
    distance[start] = 0;
    queue.offer(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();

        for (int neighbour : adj.get(node)) {
            if (distance[neighbour] == -1) {
                distance[neighbour] = distance[node] + 1;
                queue.offer(neighbour);
            }
        }
    }
    return distance;
}

distance doubles as the visited marker, so no separate array is needed.

Why it finds shortest paths

Because nodes come out of the queue in order of distance, the first time you reach a node is by the fewest possible edges. There is no shorter route still to be discovered — anything shorter would have been dequeued earlier.

This is the property depth-first search lacks. DFS reaches nodes in whatever order its recursion happens to take, so its first arrival is not necessarily the shortest.

distance[neighbour] = distance[node] + 1;
queue.offer(neighbour);                    // both together

BFS gives shortest paths only when every edge counts the same. With varying edge costs — distances, travel times, fuel — the fewest-edges route may not be the cheapest, and you need Dijkstra’s algorithm instead.

On a grid

Most BFS you write will be on a grid, where neighbours are computed rather than stored.

static int shortestPath(char[][] grid, int startR, int startC, int endR, int endC) {
    int rows = grid.length, cols = grid[0].length;
    int[][] dist = new int[rows][cols];
    for (int[] row : dist) Arrays.fill(row, -1);

    int[] dr = {-1, 1, 0, 0};
    int[] dc = {0, 0, -1, 1};

    Queue<int[]> queue = new ArrayDeque<>();
    dist[startR][startC] = 0;
    queue.offer(new int[]{startR, startC});

    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        int r = cell[0], c = cell[1];

        if (r == endR && c == endC) return dist[r][c];   // arrived

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];

            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (grid[nr][nc] == '#' || dist[nr][nc] != -1) continue;

            dist[nr][nc] = dist[r][c] + 1;
            queue.offer(new int[]{nr, nc});
        }
    }
    return -1;                            // unreachable
}

Storing coordinates as a two-element int[] avoids defining a class. Bounds checks come before reading the grid, as always.

Recovering the path

Distance alone often is not the answer — you may need the actual route. Record where each node was first reached from:

int[] parent = new int[n];
Arrays.fill(parent, -1);

// inside the neighbour loop:
if (distance[neighbour] == -1) {
    distance[neighbour] = distance[node] + 1;
    parent[neighbour] = node;             // remember how we got here
    queue.offer(neighbour);
}

Then walk backwards from the destination and reverse:

static List<Integer> pathTo(int target, int[] parent) {
    List<Integer> path = new ArrayList<>();
    for (int at = target; at != -1; at = parent[at]) {
        path.add(at);
    }
    Collections.reverse(path);
    return path;
}

If the target was never reached its parent is still -1, so check the distance before trusting the path.

Multi-source BFS

Sometimes you want the distance from the nearest of several starting points — how far each cell is from any exit, say. Rather than running BFS once per source, seed the queue with all of them at distance 0:

for (int[] source : sources) {
    dist[source[0]][source[1]] = 0;
    queue.offer(source);
}
// then the identical loop

Everything else is unchanged, and one pass gives every cell its distance to the closest source. This is a genuinely useful trick that is not obvious the first time.

Level by level

To know which “ring” you are processing, capture the queue size before draining it:

int steps = 0;
while (!queue.isEmpty()) {
    int levelSize = queue.size();         // fixed before adding the next ring

    for (int i = 0; i < levelSize; i++) {
        int node = queue.poll();
        // ... offer neighbours
    }
    steps++;
}

Reading queue.size() directly in the inner condition would include nodes added during the loop, merging the levels.

BFS or DFS

Next

Related