Solution

You'll walk a directed graph outward from a start vertex, visiting every reachable node exactly once, in order of distance from the start.

The problem, in plain English

Imagine a network — pages linking to other pages, employees reporting to managers, cities connected by one-way roads. You're standing at one node and asked: visit everyone you can reach, but visit the people closest to you first. Direct connections (one hop away) come before friends-of-friends (two hops away), and so on. Breadth-first search is the algorithm for that. The output is a list of nodes in the order you first discovered them.

Two things make it interesting beyond "loop through neighbors": the graph can have cycles (so you must not revisit nodes), and "closest first" has to be enforced (you can't just dive into the first neighbor's subgraph and lose the level discipline).

The mental model

Picture the graph laid out by distance. The start node sits at level 0. Every node one edge away sits at level 1. Every node two edges away sits at level 2. BFS visits the entire level-1 band before touching anything at level 2, then drains level 2 before reaching level 3.

The tool that enforces "level 1 before level 2" is a FIFO queue — first in, first out. When you discover a node, you add it to the back. When you process the next node, you take from the front. Because B and C entered the queue before any of B's or C's children, B and C will both be processed before any of those children touch the output. That's what produces level-by-level order without any explicit "level" bookkeeping.

A first attempt

If you've written recursive tree code, your hand might want to write this:

function bfsBroken(graph, start) {
  const order = [];
  const visited = new Set();

  function visit(node) {
    if (visited.has(node)) return;
    visited.add(node);
    order.push(node);
    for (const next of graph.get(node) || []) {
      visit(next); // recurse straight into each neighbor
    }
  }

  visit(start);
  return order;
}

On the graph from the diagram (A → B,C; B → D; C → D,E), this returns ['A', 'B', 'D', 'C', 'E']. Notice D snuck in before C — we walked all the way down B's subtree before ever touching C. That's depth-first search, not breadth-first. The recursion stacks deeper calls on top of the current one, so the most recently discovered neighbor is processed next — exactly the wrong order for BFS.

The fix isn't to patch the recursion; recursion's call stack is a LIFO stack by nature, and BFS needs FIFO. Throw the recursion out and use an explicit queue.

The working solution

function breadthFirstSearch(graph, start) {
  const order = [];          // nodes in the order we first see them
  const visited = new Set(); // prevents revisits, including under cycles
  const queue = [start];     // FIFO of nodes still to process

  // Mark start as visited BEFORE the loop, not when we shift it.
  // If we waited, a neighbor pointing back at start would re-enqueue
  // it before we ever processed it, producing a duplicate.
  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift(); // take from the FRONT — this is what makes it BFS
    order.push(node);

    // `graph.get(node) || []` tolerates nodes that have no entry
    // in the adjacency Map (sinks, or terminal cycle targets).
    const neighbors = graph.get(node) || [];
    for (const next of neighbors) {
      if (visited.has(next)) continue; // skip cycles + diamond duplicates
      visited.add(next);               // mark on DISCOVERY, not on processing
      queue.push(next);                // add to the BACK
    }
  }

  return order;
}

module.exports = { breadthFirstSearch };

Two design decisions deserve attention. First, mark visited at enqueue time, not at dequeue time. If you wait until you shift a node off the queue, a diamond graph (A → B, C; B → D; C → D) will enqueue D twice — once from B, once from C — and you'll either visit it twice or paper over the bug with an extra check inside the loop. Marking on discovery prevents the double-enqueue at its source.

Second, the queue is a plain array with push and shift. That's a fine choice for teaching and small-to-mid graphs; shift is O(n) in the worst case because the runtime may have to move every remaining element, but for graphs that fit comfortably in memory the constant is small. Real-world implementations swap in a linked-list queue or a head-pointer trick to get true O(1) dequeues — see Going further.

Walking through one call

Run breadthFirstSearch(graph, 'A') on the graph from the mental-model diagram: A → B, C, B → D, C → D, E.

Step by step:

1. Seed. queue = [A], visited = {A}, order = [].
2. Shift A. order = ['A']. Neighbors are [B, C]. Neither is visited, so mark both and push: queue = [B, C], visited = {A, B, C}.
3. Shift B. order = ['A', 'B']. Neighbors are [D]. D is unvisited — mark and push: queue = [C, D], visited = {A, B, C, D}.
4. Shift C. order = ['A', 'B', 'C']. Neighbors are [D, E]. D is already in visited — skip. E is new — mark and push: queue = [D, E], visited = {A, B, C, D, E}.
5. Shift D. order = ['A', 'B', 'C', 'D']. Neighbors: []. Nothing to enqueue. queue = [E].
6. Shift E. order = ['A', 'B', 'C', 'D', 'E']. Neighbors: []. queue = [].

The while condition fails. Return ['A', 'B', 'C', 'D', 'E']. Notice that D was reachable from both B and C, but only entered the queue once — because we marked it visited at the moment of discovery (in step 3), the second discovery in step 4 was a no-op.

Complexity. Time: O(V + E). Each vertex is added to the queue once (and shifted off once), and each directed edge is examined once when its source is processed. Space: O(V) for the queue, the visited set, and the output array combined.

Gotchas

• Recursion produces DFS, not BFS. The recursive "visit then recurse into each neighbor" pattern uses the implicit call stack — a LIFO. BFS needs FIFO. If you find yourself writing function visit(node) and recursing inside the neighbor loop, stop and reach for an explicit queue.shift() instead.
• Marking visited at dequeue time instead of enqueue time. On any graph where two parents share a child (a diamond), this double-enqueues the child. You either get duplicate entries in the output or have to add a second guard inside the loop. Mark when you discover the node, not when you process it.
• Forgetting cycle protection. Drop the visited check and a cycle like A → B → C → A becomes an infinite loop — A gets re-enqueued every time C is processed. The visited Set is the only thing standing between you and RangeError: heap out of memory.
• shift() is not O(1) on a JS array. For teaching this is fine; for a graph with millions of nodes, it dominates runtime. A simple alternative is to keep an integer head index and read queue[head++] instead of mutating the array — same algorithm, O(1) per dequeue, at the cost of leaving stale references behind that the GC eventually cleans up.
• graph.get(node) can return undefined. Adjacency maps often omit sink nodes (nodes with no outgoing edges) entirely. The || [] fallback makes that case a no-op instead of a TypeError: Cannot read properties of undefined. The alternative is requiring every node to have an entry, even if it's [] — but then your callers have to remember to seed those entries.

Going further

• Track depth alongside each node — enqueue [node, depth] pairs (or push a sentinel value between levels). Once you have depth per node, BFS doubles as a shortest-path algorithm on unweighted graphs: the first time you discover a target node is along its shortest path from the start. Returning a parent-pointer map alongside the visit order lets you reconstruct that path.
• Bidirectional BFS. Run two BFS searches simultaneously — one from the start, one from the target — and stop when their frontiers meet. On large graphs with a known target, this can be dramatically faster than one-sided BFS because each frontier only has to grow to half the total depth.
• Iterative deepening DFS as a BFS substitute. When memory matters more than wall-clock time (a BFS queue can balloon on wide graphs), iterative deepening runs DFS with a depth cap of 1, then 2, then 3, and so on. It revisits work but uses only O(d) memory for depth d, versus O(V) for BFS.