Breadth-First Search

Breadth-first search explores a graph level by level: everything one step from the start, then everything two steps away, and so on. That ordering is not a stylistic choice — it is what makes BFS find shortest paths, and no other traversal does.

The algorithm

        Set<String> visited = new HashSet<>();
        Deque<String> queue = new ArrayDeque<>();

        visited.add(start);
        queue.add(start);

        while (!queue.isEmpty()) {
            String current = queue.remove();
            order.add(current);
            for (String next : neighbours(current)) {
                if (visited.add(next)) {   // add() returns false if it was already there
                    queue.add(next);
                }
            }
        }

Take from the front, add neighbours to the back. Because the queue is FIFO, everything at distance 1 is dequeued before anything at distance 2 — the level ordering falls out of the container rather than needing to be arranged.

visited.add(next) returning false when the element was already present means the check and the marking are one operation. Writing contains then add is two lookups doing one job.

⚠️ Mark visited on enqueue, not on dequeue

This is the mistake that matters, and it is easy to make because the wrong version still produces correct output.

If you mark a vertex visited only when you dequeue it, then between enqueueing and processing it, every neighbour that also points at it will enqueue it again. On a dense graph the queue fills with duplicates and the work blows up — not by a constant factor, but exponentially in the worst case. The answer stays right; the running time does not.

Mark on enqueue and every vertex enters the queue exactly once, giving the complexity BFS is supposed to have.

Complexity

O(V + E) time — every vertex is enqueued once and every edge examined once. O(V) space for the queue and the visited set.

The worst case for the queue is a wide graph: a vertex with a million neighbours puts a million entries in the queue at once. That is the practical difference from DFS, whose memory scales with depth rather than width.

Shortest paths, for free

Because BFS reaches every vertex by the fewest possible edges, the first time it arrives somewhere is along a shortest path. Recording how you arrived is all that is needed:

        Map<String, String> cameFrom = new HashMap<>();
        Set<String> visited = new HashSet<>();
        Deque<String> queue = new ArrayDeque<>();
        visited.add(from);
        queue.add(from);

        while (!queue.isEmpty()) {
            String current = queue.remove();
            if (current.equals(to)) {
                List<String> path = new ArrayList<>();
                for (String at = to; at != null; at = cameFrom.get(at)) {
                    path.add(at);
                }
                java.util.Collections.reverse(path);
                return path;
            }
            for (String next : neighbours(current)) {
                if (visited.add(next)) {
                    cameFrom.put(next, current);
                    queue.add(next);
                }
            }
        }

The cameFrom map stores each vertex's predecessor. Once the target is reached, walk those links back to the start and reverse. The loop terminates because the start has no predecessor, so cameFrom.get returns null.

        Check.eq(g.shortestPath("a", "e").toString(), "[a, b, e]", "shortest path");
        Check.eq(g.shortestPath("a", "a").toString(), "[a]", "path to self");
        Check.eq(g.shortestPath("a", "f").toString(), "[]", "no path to an isolated vertex");

Returning an empty list for "unreachable" rather than null keeps callers simple — and connected() is then one line on top of it.

⚠️ Unweighted only

BFS finds the path with the fewest edges. On a weighted graph that is usually not the cheapest path — three short hops can easily beat one long one, and BFS will confidently return the one-hop route.

It does not fail or warn. It answers a different question from the one you meant. For weighted graphs you need Dijkstra, which is BFS with the queue replaced by a priority queue ordered by distance-so-far. Seen that way, BFS is just Dijkstra where every edge costs 1 — and a plain FIFO queue is already ordered by distance when all edges are equal.

Level-by-level processing

Sometimes you need to know which level you are on — "friends of friends", or the minimum number of moves. The trick is to record the queue's size before processing a level, then handle exactly that many:

while queue is not empty:
    levelSize = queue.size()
    for i in 0 .. levelSize:
        process one vertex, enqueue its neighbours
    depth = depth + 1

Everything enqueued during that pass belongs to the next level, and the snapshot of the size is what keeps the two from mixing.

BFS or DFS?

That last row is about memory. BFS holds a whole level at once, so a wide graph is expensive; DFS holds one path, so a deep graph is expensive. Pick against the shape you have.

Where BFS shows up

• Shortest path in unweighted graphs — the headline use.
• Degrees of separation — social distance between two people.
• Web crawling — pages close to the seed first.
• Grid problems — shortest route through a maze, flood fill, "number of islands". A grid is a graph where each cell's neighbours are the cells beside it.
• Puzzle solving — fewest moves to a solved state.

What to remember

• A queue, and the level ordering follows.
• Mark visited on enqueue, or vertices are queued repeatedly.
• O(V + E) time, O(V) space; the queue holds a whole level.
• Shortest path in an unweighted graph — record predecessors and walk back.
• Weighted graphs need Dijkstra; BFS is the special case where every edge costs 1.