Implement Breadth-First Search

Given a directed graph with n vertices numbered 0 to n - 1, return its vertices in breadth-first order:

• Start at vertex 0.
• Visit a vertex's neighbors in the order they appear in its adjacency list.
• If some vertices can't be reached, start again from the lowest-numbered vertex that hasn't been visited, until every vertex is visited.

Example

graph LR
    0 --> 1
    0 --> 2
    1 --> 3
    2 --> 3
    3 --> 4
    5 --> 4

Adjacency list:  0: [1, 2]   1: [3]   2: [3]   3: [4]   4: []   5: [4]
Output:          [0, 1, 2, 3, 4, 5]

Vertex 0 reaches 1 and 2 first (distance 1), then 3 (distance 2), then 4 (distance 3). No edge leads into 5, so it's visited last, as the start of a second search.

How BFS works

BFS explores the graph in rings around the start vertex: first every vertex one edge away, then every vertex two edges away, and so on. A queue (first in, first out) produces that order:

1. Mark the start vertex visited and add it to the queue.
2. Take the vertex at the front of the queue and append it to the output.
3. For each neighbor that hasn't been visited, mark it visited and add it to the back of the queue.
4. Repeat steps 2 and 3 until the queue is empty.

Mark a vertex visited when you add it to the queue, not when you take it out. In the example, 3 is a neighbor of both 1 and 2. If you only marked vertices when removing them, 3 would be queued twice.

Walkthrough from vertex 0:

Brute force: an ArrayList as the queue

The algorithm above is already the right one. The brute-force part is the data structure: using an ArrayList (a resizable array) and removing from the front with remove(0). The graph is a List<List<Integer>>: entry v is the list of neighbors of v.

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<Integer> bfs(List<List<Integer>> adj) {
        int n = adj.size();
        boolean[] visited = new boolean[n];
        List<Integer> order = new ArrayList<>();

        for (int start = 0; start < n; start++) {
            if (visited[start]) continue;
            visited[start] = true;
            List<Integer> queue = new ArrayList<>();
            queue.add(start);
            while (!queue.isEmpty()) {
                int v = queue.remove(0); // shifts every remaining element left
                order.add(v);
                for (int w : adj.get(v)) {
                    if (!visited[w]) {
                        visited[w] = true;
                        queue.add(w);
                    }
                }
            }
        }
        return order;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = List.of(List.of(1, 2), List.of(3), List.of(3), List.of(4), List.of(), List.of(4));
        System.out.println(bfs(adj));
    }
}

[0, 1, 2, 3, 4, 5]

Time: O(V² + E). Each remove(0) moves every element behind it, and the queue can hold up to V vertices. Space: O(V) for visited and the queue.

Optimal: ArrayDeque

ArrayDeque is a ring buffer. poll removes from the front by moving its start index instead of shifting elements, so it's O(1). add appends at the back, and poll returns null when the queue is empty.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class Main {
    static List<Integer> bfs(List<List<Integer>> adj) {
        int n = adj.size();
        boolean[] visited = new boolean[n];
        List<Integer> order = new ArrayList<>();
        Queue<Integer> queue = new ArrayDeque<>();

        for (int start = 0; start < n; start++) {
            if (visited[start]) continue;
            visited[start] = true;
            queue.add(start);

            while (!queue.isEmpty()) {
                int v = queue.poll();
                order.add(v);
                for (int w : adj.get(v)) {
                    if (!visited[w]) {
                        visited[w] = true;
                        queue.add(w);
                    }
                }
            }
        }
        return order;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = List.of(List.of(1, 2), List.of(3), List.of(3), List.of(4), List.of(), List.of(4));
        System.out.println(bfs(adj));

        List<List<Integer>> cycle = List.of(List.of(1), List.of(2), List.of(0)); // 0 -> 1 -> 2 -> 0
        System.out.println(bfs(cycle));
        System.out.println(bfs(List.of()));
    }
}

[0, 1, 2, 3, 4, 5]
[0, 1, 2]
[]

Time: O(V + E). Every vertex enters the queue once, and every edge is looked at once, when its source vertex is taken from the queue. Space: O(V).

The cycle example shows why visited is required: without it, 0 -> 1 -> 2 -> 0 would loop forever.

Edge cases

• Empty graph (n = 0): the outer loop doesn't run, and the result is [].
• Unreachable vertices: the outer for loop over start picks them up.
• Self-loops and duplicate edges: visited makes them harmless.
• Distances: BFS visits vertices in order of their distance from the start, which makes it the standard tool for shortest paths in unweighted graphs. Store dist[w] = dist[v] + 1 when you queue w.