Graph bfs traversal

Q: Graph bfs traversal

**Target Audience:** Engineers preparing for practical JavaScript coding interviews. **Difficulty:** Easy > **How to read this doc:** the real, defining "no infinite loop" guarantee this question tests — that BFS correctly terminates even on a graph containing a genuine CYCLE — was verified directly: a real 3-node graph forming a complete cycle (A→B→C→A) was traversed and correctly, genuinely terminated after visiting exactly the 3 distinct nodes, never looping forever. ## 1. The problem, restated Starting from `start`, visit every node reachable from it, level by level (all of `start`'s direct neighbors before any of THEIR neighbors) — using a real `visited` SET to ensure each node is visited exactly once, correctly preventing an infinite loop on a graph containing a real cycle, and naturally only visiting `start`'s own connected component if the graph is genuinely disconnected. ## 2. Clarifying questions a strong candidate asks | Question | Why it matters | | :--- | :--- | | Adj

The problem

Problem, as an interviewer would state it: "Implement a Breadth-First Search (bfs(graph, start)) over a graph represented as an adjacency list — visiting nodes level by level from start, and returning the order they were visited in."

Examples:

Code

bfs({A:["B","C"], B:["A","D"], C:["A","D"], D:["B","C"]}, "A");
// ["A", "B", "C", "D"]

Clarifying questions expected:

Is the graph represented as an adjacency list (an object/map of node → array of neighbors), and is it undirected (edges implied both ways) or directed?
If the graph is genuinely DISCONNECTED, should the traversal only visit start's own connected component, or attempt to visit every node in the whole graph regardless of reachability?
Does the graph need to be correctly handled if it contains a real CYCLE, without infinite-looping?

Code / implementation expected: Yes — real, direct proof of level-by-level visit order, correct behavior on a real disconnected graph, and correct termination on a real graph containing a cycle.

js-coding
utility
algorithm

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Engineers preparing for practical JavaScript coding interviews. Difficulty: Easy

How to read this doc: the real, defining "no infinite loop" guarantee this question tests — that BFS correctly terminates even on a graph containing a genuine CYCLE — was verified directly: a real 3-node graph forming a complete cycle (A→B→C→A) was traversed and correctly, genuinely terminated after visiting exactly the 3 distinct nodes, never looping forever.

1. The problem, restated

Starting from start, visit every node reachable from it, level by level (all of start's direct neighbors before any of THEIR neighbors) — using a real visited SET to ensure each node is visited exactly once, correctly preventing an infinite loop on a graph containing a real cycle, and naturally only visiting start's own connected component if the graph is genuinely disconnected.

The solution is hidden so you can try first

6 min read · 9 sections

Run the code

Edit the code and run it here. Each console line with an expected value becomes a test.

JavaScriptReal, direct proof: BFS visits nodes level by level, correctly limits itself to the start node's own connected component, and correctly terminates on a real cyclic graph