Graph Traversal - Breadth First Search (BFS)

BFS explores a graph outward in concentric rings: it visits every vertex at distance k from the source before touching any vertex at distance k+1, by using a FIFO queue so vertices are processed in the exact order they were first discovered. This first-discovery order is what guarantees the ring-by-ring behaviour and makes BFS the algorithm of choice for shortest paths when every edge costs the same.

Recognize the pattern

• "Shortest path / fewest edges / minimum number of moves" in an unweighted graph or implicit graph (grid, word ladder, puzzle states).
• "Level order" traversal of a tree, or "minimum number of steps to reach every node."
• Multi-source shortest distance (e.g., rotting oranges, nearest exit) — seed the queue with several starts at once.
• Any question phrased as "is X reachable from Y in the fewest hops" rather than "does a path exist."

Brute force → optimal

Brute force: to find the shortest-hop distance between two vertices you could enumerate all simple paths (DFS with backtracking) and take the minimum length — exponential, O(V!) in the worst case, because paths are re-explored with no memory of what's already the shortest way in.

Optimal (BFS): process vertices in strict order of discovery using a queue and a visited set. The first time a vertex is dequeued/enqueued, that distance is already minimal — no vertex is ever revisited with a shorter distance later, so each vertex and edge is examined a constant number of times. This turns exponential path enumeration into a single linear pass, O(V + E).

Complexity, derived

Time: each vertex is enqueued exactly once (guarded by the visited check) and dequeued exactly once → O(V) queue operations. When a vertex is dequeued, its full adjacency list is scanned once; summed over all vertices this touches each directed edge exactly once (each undirected edge twice) → O(E). Total: O(V + E).

Space: the visited array is O(V). The queue holds at most one full "frontier" (level) of vertices — in the worst case (e.g., a star graph) that frontier is O(V). Total: O(V) auxiliary space, plus O(V+E) for the adjacency-list representation itself.

Worked example

Graph: vertices {0,1,2,3,4}, edges (0,1),(0,2),(0,3),(1,2),(2,4). Start = 0.

Visit order: 0, 1, 2, 3, 4 — grouped exactly by distance from 0: {0} at distance 0, {1,2,3} at distance 1, {4} at distance 2.

Java implementation

import java.util.*;

class BFS {
    // adj: adjacency list, n vertices, returns visit order from start
    static List<Integer> bfs(List<List<Integer>> adj, int n, int start) {
        boolean[] visited = new boolean[n];
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        Queue<Integer> queue = new ArrayDeque<>();
        List<Integer> order = new ArrayList<>();

        visited[start] = true;
        dist[start] = 0;
        queue.add(start);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            order.add(current);
            for (int neighbor : adj.get(current)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    dist[neighbor] = dist[current] + 1;
                    queue.add(neighbor);
                }
            }
        }
        return order;
    }
}

Key detail: mark visited[neighbor] = true at enqueue time, not at dequeue time — otherwise the same neighbor can be pushed onto the queue multiple times by different frontier vertices before it is ever processed, wasting time and space (and breaking the O(V+E) bound).

Pitfalls

• Marking visited on dequeue instead of enqueue — duplicates flood the queue, degrading to O(E·V) in dense graphs and letting nodes be added several times.
• Disconnected graphs — a single BFS from one source misses unreachable components; loop over all vertices and BFS from each unvisited one if full coverage is required.
• Using BFS for weighted shortest paths — BFS assumes unit edge weight; on weighted graphs it gives the fewest-edges path, not the lightest one (use Dijkstra/Bellman-Ford instead).
• Recursion instead of an explicit queue — BFS is not naturally recursive; forcing recursion loses the level-order guarantee and clarity.

When to use / when not — trade-offs

Use BFS when you need shortest path / minimum steps in an unweighted graph, level-order processing, or to find connected components/bipartiteness.

Prefer DFS instead when you only need reachability, topological order, cycle detection, or path enumeration/backtracking — DFS uses O(depth) stack space versus BFS's O(width-of-frontier) queue space, which matters on wide shallow graphs where BFS's memory footprint can dwarf DFS's.

Prefer Dijkstra instead of BFS when edges carry positive weights — Dijkstra generalizes BFS's frontier idea using a priority queue keyed by accumulated distance, at O((V+E) log V) instead of O(V+E).

Takeaways

• BFS's queue enforces first-discovered-first-processed order, which is exactly what makes distances come out correct and monotonic.
• Mark visited at enqueue time, always — this is the single most common correctness bug.
• O(V+E) time and O(V) space fall directly out of "each vertex enqueued once, each edge scanned once."
• BFS = shortest hops on unweighted graphs; reach for Dijkstra the moment edges have weights.

Recall: Why must a vertex be marked visited when it is enqueued rather than when it is dequeued?

Synthesized from graph traversal fundamentals (CLRS-style BFS analysis) and standard interview-prep BFS references.