BFS Visualization for Coding Interviews

By Rahul Kumar · Senior Software Engineer · Updated May 2026 · Category: Graphs

Level-order walk; shortest path in unweighted graph.

Concept

Breadth-First Search is the workhorse traversal for unweighted shortest paths and layer-by-layer exploration. Starting from a source vertex, BFS expands outward one hop at a time, visiting every vertex at distance k before any vertex at distance k+1. The discipline comes from a FIFO queue: you enqueue a vertex the first time you see it, mark it visited so you never enqueue it twice, and dequeue to pull the next frontier. Because every edge is treated as unit weight, the depth at which BFS first reaches a vertex is exactly the shortest hop count to it. That single property powers an absurd number of interview answers: shortest path in a grid, level-order traversal, bipartite check, word ladder, minimum steps in a state-space search. On an adjacency list, BFS runs in O(V+E) time and O(V) extra space, and it is usually the first algorithm you should reach for when edges are unweighted.

BFS — Interactive Simulator

Runs fully client-side in your browser; no sign-up. Or open full screen →

Launch the interactive BFS visualization — animated algorithm, step-through, and live data-structure updates.

How it works

The algorithm maintains three pieces of state: a visited set, a distance array, and a queue. Push the source, mark it visited, record distance 0. In a loop, pop the front vertex u, iterate its neighbors, and for each unvisited neighbor v, mark it, set dist[v] = dist[u] + 1, and push it to the back of the queue. When the queue drains, dist[] holds the hop count from the source to every reachable vertex; unreachable vertices keep their sentinel of -1 or infinity. The correctness argument is an invariant: at any point the queue contains vertices from at most two consecutive BFS layers, and vertices are popped in non-decreasing distance order. That monotonicity is why BFS gives shortest paths for unit edges but collapses the moment edges carry weights - the first time you reach a vertex may not be via the cheapest path once hop count and cost diverge. For path reconstruction, store a parent[] array alongside dist[] and walk backwards from the target. For multi-source BFS, seed the queue with every source at distance 0 before you start; the algorithm then computes shortest distance to the nearest source for every vertex in one pass.

Implementation

BFS on an adjacency list returning shortest-hop distances

import java.util.*;

public class BFS {
    /** Returns dist[v] = shortest number of edges from src to v, or -1 if unreachable. */
    public static int[] bfs(List<List<Integer>> adj, int src) {
        int n = adj.size();
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        dist[src] = 0;

        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.offer(src);

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adj.get(u)) {
                if (dist[v] == -1) {          // first time we see v
                    dist[v] = dist[u] + 1;
                    queue.offer(v);
                }
            }
        }
        return dist;
    }

    /** Reconstruct the shortest path from src to target using a parent array. */
    public static List<Integer> shortestPath(List<List<Integer>> adj, int src, int target) {
        int n = adj.size();
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        parent[src] = src;

        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.offer(src);

        while (!queue.isEmpty()) {
            int u = queue.poll();
            if (u == target) break;
            for (int v : adj.get(u)) {
                if (parent[v] == -1) {
                    parent[v] = u;
                    queue.offer(v);
                }
            }
        }
        if (parent[target] == -1) return List.of();
        LinkedList<Integer> path = new LinkedList<>();
        for (int cur = target; cur != src; cur = parent[cur]) path.addFirst(cur);
        path.addFirst(src);
        return path;
    }
}

Complexity

Time: O(V + E)
Space: O(V)

Common pitfalls

Marking a vertex visited only when you pop it instead of when you enqueue it, which allows duplicates on the queue and blows up runtime.
Using BFS on a weighted graph expecting shortest path - the first visit is shortest in edges, not in cost.
Forgetting that an undirected edge appears twice in the adjacency list; iterating it is fine, but do not double-count when summing degrees.
Using a LinkedList-based Queue when ArrayDeque is faster and has no null-permission surprises.
Losing the parent pointer when you need the actual path, not just the distance.

Key design decisions & trade-offs

Queue vs recursion — Chosen: Explicit FIFO queue. BFS is inherently iterative; recursion would invert the layering and give you DFS semantics.
Visited encoding — Chosen: dist[] doubling as visited flag. A single int[] with -1 sentinel saves a parallel boolean[] and a branch. If you need distances anyway, it is free.
Adjacency representation — Chosen: List<List<Integer>>. Sparse graphs dominate in practice; adjacency lists iterate only real neighbors, while an adjacency matrix costs O(V) per expansion.

Practice problems

Interview follow-ups

0-1 BFS using a deque when edges have weights 0 or 1.
Multi-source BFS for problems like "nearest gate" on a grid.
Bidirectional BFS to shrink the search frontier for shortest-path queries.
BFS on implicit graphs such as state-space puzzles (sliding tile, word ladder).
Bipartite check via two-coloring during BFS.

Why it matters

BFS is a core part of the Graphs toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".