Breadth-First Search Visualizer

Breadth-first search explores a graph in rings. It visits everything one step from the start, then everything two steps away, then three — never moving outward until the current ring is fully explored. That ordering is not a stylistic choice; it is what makes BFS the correct algorithm for finding shortest paths when every edge costs the same.

The implementation difference between BFS and depth-first search is a single word: BFS takes the *oldest* node from its frontier, DFS takes the *newest*. Swap a queue for a stack and one algorithm becomes the other. Almost everything else about them — the traversal order, what they are good for, the shape of the tree they produce — follows from that one decision.

What is breadth-first search?

BFS explores a graph level by level from a starting node. It maintains a queue of discovered but not yet processed nodes, and a visited set so no node is handled twice. Repeatedly, it dequeues the front node, examines every neighbour, and enqueues any that have not been seen before.

Because a queue is first-in-first-out, nodes leave it in the order they were discovered. Nodes at distance 1 are all discovered before any node at distance 2, so they all leave the queue first. This is the mechanical reason the traversal proceeds in rings.

The visited set is not an optimisation — it is required for termination. A graph with a cycle would send BFS around it forever without one, and even in an acyclic graph the same node can be reachable through several paths, which would cause exponential re-exploration.

Why BFS finds shortest paths

The claim is: on an unweighted graph, the first time BFS reaches a node is via a shortest path from the start. This is the single most important property of the algorithm, and it deserves an argument rather than an assertion.

The invariant is that the queue always holds nodes of at most two distinct distances, d and d+1, with all the d nodes ahead of all the d+1 nodes. Initially the queue holds only the start at distance 0. When a node at distance d is dequeued, its undiscovered neighbours are recorded at distance d+1 and appended to the back — behind every remaining d node and level with the other d+1 nodes. The invariant holds.

Now suppose some node v is first discovered at distance d+1, but a shorter path of length k ≤ d exists. That path's second-to-last node u would sit at distance k−1 < d, and u would have been dequeued before any node at distance d — at which point v would have been discovered then, not later. Contradiction. So the first discovery is always shortest.

This argument depends entirely on every edge having the same cost. As soon as edges have different weights, 'fewest edges' and 'lowest total cost' stop being the same question, and BFS answers the wrong one. That is where Dijkstra's algorithm takes over.

Step-by-step walkthrough

Take a graph where A connects to B and C; B connects to D; C connects to D and E. Start at A.

1. Enqueue A at distance 0. Queue: [A].
2. Dequeue A. Its neighbours B and C are undiscovered, so record both at distance 1 and enqueue them. Queue: [B, C].
3. Dequeue B. Its neighbour D is new — distance 2, enqueued. Queue: [C, D].
4. Dequeue C. Neighbour D is already discovered, so skip it; E is new at distance 2. Queue: [D, E]. Note that D keeps distance 2 via B — the later route through C offers nothing shorter.
5. Dequeue D, then E. Neither has undiscovered neighbours. The queue empties and the traversal ends with distances A=0, B=1, C=1, D=2, E=2.

BFS or DFS?

The choice is rarely about taste. Each answers questions the other cannot answer efficiently.

Use BFS when you need the shortest path in an unweighted graph, when you want nodes grouped by distance, when the target is likely near the start, or when the graph is very deep — BFS has no recursion depth to overflow.

Use DFS when you need to explore an entire structure, detect cycles, produce a topological ordering, find connected components, or when the graph is very wide. DFS's memory holds one path; BFS's holds an entire level.

The memory profile is the practical difference people underestimate. On a branching graph, the widest level can contain a large fraction of all nodes, so BFS's queue can grow to O(V). DFS's stack only ever holds the current path, which is O(depth). Searching a game tree breadth-first is usually impossible for this reason, while searching it depth-first is routine.

How the animation above works

The queue panel is the thing to watch. Nodes enter at the right and leave from the left, and the distance labels above each node show the ring structure emerging — every node at distance 1 turns mint before any node at distance 2 does.

Set a destination node and BFS stops as soon as it dequeues that node, then highlights the path in coral. Drag nodes around or delete edges and re-run: the path changes to whatever is now shortest in edge count, which is not always the one that looks shortest on screen. Geometric distance and graph distance are different things, and the visualiser makes that gap visible.

Time and space complexity

O(V + E) time with an adjacency list. Every vertex is enqueued and dequeued exactly once, giving O(V); every edge is examined exactly once from each endpoint, giving O(E). The two terms are separate because a graph can have many vertices and few edges, or the reverse.

With an adjacency matrix the cost rises to O(V²), because finding the neighbours of a node means scanning an entire row of V entries whether or not those edges exist. This is the main reason adjacency lists are the default representation for sparse graphs.

O(V) space for the visited set, the distance array and the queue. The queue's peak size is the width of the widest level, which on a branching graph can be a large fraction of V — this is BFS's practical weakness compared with DFS.

Variants worth knowing

Multi-source BFS starts with several nodes in the queue at distance 0 simultaneously. This computes, for every node, the distance to the *nearest* source — in one pass, at the same O(V + E) cost as a single-source search. It is the right tool for 'how far is each cell from the nearest exit' problems, and running BFS once per source instead is a common and expensive mistake.

Bidirectional BFS searches forward from the start and backward from the goal at once, stopping when the two frontiers meet. Since each search only needs to reach halfway, the explored volume drops from roughly b^d to 2·b^(d/2) — an enormous saving on large graphs, and the technique behind fast social-network degree-of-separation queries.

0-1 BFS handles graphs whose edges cost either 0 or 1, using a double-ended queue: zero-weight edges push to the front, one-weight edges to the back. This keeps the O(V + E) bound where Dijkstra would cost O(E log V).

Complexity at a glance

The numbers below are what the counters in the visualiser converge on. Raise the array size and watch the comparison count grow at the rate this table predicts.

Pseudo code

Language-agnostic, and close enough to the implementations below that you can read them side by side.

Breadth-First Search in five languages

Working reference implementations — copy or download any of them. They are written to be read, so the comments explain the decisions rather than restating the code.

/**
 * BFS over an adjacency list. Returns distances (in edges) and the parent
 * map, from which any shortest path can be reconstructed.
 */
function bfs(graph, start) {
  const visited = new Set([start]);
  const distance = new Map([[start, 0]]);
  const parent = new Map();
  const queue = [start];
  let head = 0; // index-based dequeue: shift() is O(n) on large arrays

  while (head < queue.length) {
    const node = queue[head++];

    for (const neighbour of graph.get(node) ?? []) {
      if (visited.has(neighbour)) continue;

      // Marking here, not on dequeue, keeps each node in the queue once.
      visited.add(neighbour);
      distance.set(neighbour, distance.get(node) + 1);
      parent.set(neighbour, node);
      queue.push(neighbour);
    }
  }

  return { distance, parent };
}

/** Walk the parent map back from the goal to recover the path. */
function shortestPath(parent, start, goal) {
  const path = [goal];
  let cursor = goal;

  while (cursor !== start) {
    if (!parent.has(cursor)) return null; // unreachable
    cursor = parent.get(cursor);
    path.unshift(cursor);
  }

  return path;
}

const graph = new Map([
  ["A", ["B", "C"]],
  ["B", ["A", "D"]],
  ["C", ["A", "D", "E"]],
  ["D", ["B", "C"]],
  ["E", ["C"]],
]);

const { distance, parent } = bfs(graph, "A");
console.log([...distance]); // A:0, B:1, C:1, D:2, E:2
console.log(shortestPath(parent, "A", "E")); // ["A", "C", "E"]

Advantages and disadvantages

Real-world applications

• Shortest path in unweighted graphs — maze solving, grid pathfinding, puzzle states where every move costs the same.
• Social network degree-of-separation queries, usually bidirectionally so both frontiers only travel half the distance.
• Web crawlers, which explore pages level by level from a set of seeds to prioritise breadth of coverage.
• Network broadcast and flood-fill algorithms, including the paint-bucket tool in image editors.
• Finding connected components and testing bipartiteness by two-colouring alternate levels.
• GPS and routing systems on unweighted segments, and the BFS layer inside the Edmonds–Karp maximum-flow algorithm.
• Multi-source distance maps — 'distance from every cell to the nearest exit' — computed in a single pass.

Interview questions

The questions that actually get asked about Breadth-First Search, with the answers an interviewer is listening for.

1. Q1. Why does BFS find the shortest path in an unweighted graph but not in a weighted one?

   BFS explores strictly in order of increasing edge count, so the first time it reaches a node is via the fewest edges. In an unweighted graph fewest edges means shortest. In a weighted graph the cheapest path may use more edges than a costlier one — three edges of weight 1 beat one edge of weight 10 — so 'fewest edges' answers a different question. Dijkstra's algorithm fixes this by taking the lowest cumulative cost rather than the oldest queue entry.

2. Q2. When should you mark a node as visited in BFS?

   When it is enqueued, not when it is dequeued. If you defer the mark, a node reachable from several already-queued nodes gets enqueued once per discoverer, so the queue can hold many duplicates and the O(V + E) bound is lost. Marking on discovery guarantees each node enters the queue exactly once.

3. Q3. What is bidirectional BFS and why is it faster?

   It runs two searches at once — forward from the start and backward from the goal — and stops when the frontiers intersect. Each search only has to cover half the distance, so the explored volume falls from roughly b^d to 2·b^(d/2). On a graph with branching factor 10 and distance 6, that is about two thousand nodes instead of a million.

4. Q4. How would you find every node within k steps of a start node?

   Run BFS and stop as soon as you dequeue a node whose distance exceeds k. Because BFS processes nodes in non-decreasing distance order, everything already dequeued is within k and nothing further needs examining. This early exit is a direct consequence of the level-by-level ordering.

5. Q5. BFS or DFS for a very deep graph, and why?

   BFS if you need a shortest path or the graph might be infinitely deep, since DFS could descend forever down one branch. DFS if the graph is deep but you need to explore all of it, because DFS's memory holds only the current path — O(depth) — while BFS's queue holds an entire level, which can be O(V).

Common mistakes

• Marking nodes visited on dequeue rather than on discovery, which allows duplicate queue entries and breaks the complexity bound.
• Using an array with shift() as the queue in JavaScript, which is O(n) per dequeue and turns the algorithm into O(V²) — use an index cursor or a proper deque.
• Using BFS on a weighted graph and reporting the result as the shortest path, which is silently wrong rather than obviously broken.
• Forgetting the visited set entirely, which loops forever on any cyclic graph.
• Recording distances only when dequeuing, so the distance map is incomplete for nodes still in the queue.
• Failing to handle disconnected graphs — BFS from one start reaches only its component, so a full traversal needs an outer loop over unvisited nodes.
• Running single-source BFS once per source when multi-source BFS would answer the same question in a single pass.

Optimisation tips

• Use a real queue: collections.deque in Python, ArrayDeque in Java, or an index cursor over an array in JavaScript.
• Use bidirectional BFS when both endpoints are known — it is the single largest win available on large graphs.
• Seed the queue with all sources at once for nearest-source problems, rather than running the search repeatedly.
• Stop as soon as the goal is dequeued rather than draining the whole queue.
• For grid graphs, index cells as row * width + col in a flat array rather than using a hash map — the constant-factor difference is large.
• For graphs with edges weighted only 0 or 1, use 0-1 BFS with a deque instead of Dijkstra, keeping the O(V + E) bound.
• Store the parent pointer rather than the full path per node; reconstructing at the end costs O(path length) instead of O(V·path) in memory.

Summary

Breadth-first search explores a graph in rings from a start node, using a FIFO queue so that everything at distance d is processed before anything at distance d+1. That ordering guarantees the first time a node is reached is via the fewest possible edges, which makes BFS the correct and complete algorithm for shortest paths in unweighted graphs.

It runs in O(V + E) time and O(V) space with an adjacency list. Its limits are equally clear: the queue can grow to the width of the widest level, and it answers the wrong question on weighted graphs, where Dijkstra's algorithm is needed instead. The two variants worth carrying around are multi-source BFS, which computes nearest-source distances in one pass, and bidirectional BFS, which cuts the explored volume dramatically when both endpoints are known.

Frequently asked questions

Related algorithms

• Depth-First Search

  Follow one branch as deep as it goes, then backtrack — a stack, or recursion.

  O(V + E)Intermediate

• Dijkstra's Algorithm

  Greedily settle the nearest unvisited node to get shortest paths on non-negative weights.

  O((V + E) log V)Advanced

• Prim's Algorithm

  Grow a minimum spanning tree outward from one node, always taking the cheapest edge out.

  O(E log V)Advanced