BFS (Breadth-First) Visualization — Step by Step

A queue drives everything

BFS explores a graph in expanding rings around the start node, and the entire behaviour comes from one choice of data structure: a FIFO [queue](/workspace/queue). Nodes are enqueued when discovered and dequeued in the same order, so nodes discovered early are processed before nodes discovered late. Combined with a *visited* set that ensures each node is handled once, this forces the traversal to finish all nodes at distance 1 before touching any node at distance 2, and so on. Swap the queue for a stack and the identical loop becomes DFS — the container *is* the algorithm.

A concrete trace

Take a five-node graph with edges 0–1, 0–4, 1–2, 1–3, and 3–4. Start BFS at node 0. Enqueue 0 → queue [0]. Dequeue 0, visit it, enqueue its neighbours 1 and 4 → queue [1, 4]. Dequeue 1, visit, enqueue its undiscovered neighbours 2 and 3 → queue [4, 2, 3]. Dequeue 4, visit — its neighbours 0 and 3 are already discovered, so nothing is added. Dequeue 2, then dequeue 3. Final visit order: 0, 1, 4, 2, 3 — both of 0's direct neighbours before any node two hops away.

Levels are distances

Label each node with the level at which BFS discovers it: node 0 is level 0; nodes 1 and 4 are level 1; nodes 2 and 3 are level 2. That level is exactly the minimum number of edges from the start — and this is BFS's superpower. Notice node 4: the path 0 → 1 → 3 → 4 also reaches it, using three edges, but BFS finds it first via the direct edge 0–4. Because all level-k nodes are processed before any level-(k+1) node, the *first* time BFS reaches a node is provably along a shortest path in edge count.

Mark nodes at discovery, not at visit

One subtlety keeps the queue clean: a node should be marked as discovered when it is enqueued, not later when it is dequeued. In the trace above, node 3 is discovered from node 1; when node 4 is processed moments later and also sees node 3, the check prevents a duplicate enqueue. Without it, popular nodes would enter the queue once per incoming edge, inflating memory and work. The visualizer shows this as the three node states — unvisited, in queue (frontier), and visited — with each enqueue and dequeue as its own step.

Why it costs O(V + E)

Every vertex enters and leaves the queue at most once — that is O(V) queue operations. Every edge is examined at most once from each endpoint when its owner is dequeued — O(E) edge inspections. Total: O(V + E), linear in the size of the graph, with O(V) extra space for the queue and visited set in the worst case. This is optimal for traversal: any algorithm that claims to explore a graph must at least look at every vertex and edge once. The cost of BFS is essentially the cost of reading the graph.

JavaScript

function bfs(graph, start) {
  // graph: Map or object mapping node -> array of neighbours
  const visited = new Set([start]);
  const queue = [start];
  const order = [];

  while (queue.length > 0) {
    const node = queue.shift(); // dequeue (FIFO)
    order.push(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor); // mark at discovery time
        queue.push(neighbor);
      }
    }
  }
  return order; // nodes in breadth-first visit order
}

Python

from collections import deque


def bfs(graph, start):
    """graph: dict mapping node -> list of neighbours."""
    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()  # dequeue (FIFO)
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)  # mark at discovery time
                queue.append(neighbor)

    return order  # nodes in breadth-first visit order

Java

import java.util.*;

public class BFS {
    // graph: adjacency list, graph.get(u) = neighbours of u
    public static List<Integer> bfs(List<List<Integer>> graph, int start) {
        boolean[] visited = new boolean[graph.size()];
        Deque<Integer> queue = new ArrayDeque<>();
        List<Integer> order = new ArrayList<>();

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

        while (!queue.isEmpty()) {
            int node = queue.poll(); // dequeue (FIFO)
            order.add(node);

            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true; // mark at discovery time
                    queue.add(neighbor);
                }
            }
        }
        return order;
    }
}