Breadth-First Search

Implement breadthFirstSearch(graph, start) — a traversal that visits every reachable node in a directed graph, expanding outward from the start vertex one level at a time. This is the classic BFS algorithm: closer nodes are visited before farther ones, and a node is never visited twice. Return the visit order as an array.

Signature

// graph: Map<NodeId, NodeId[]>  — adjacency list, each key maps to its out-neighbors
// start: NodeId                  — vertex to begin from
// returns: NodeId[]              — nodes in the order BFS first discovers them
function breadthFirstSearch(graph, start): NodeId[]

NodeId can be any value you can use as a Map/Set key (string, number). The graph is directed — if A → B is in the adjacency list, that does NOT imply B → A.

Examples

// Simple line graph: A → B → C → D
const g1 = new Map([
  ['A', ['B']],
  ['B', ['C']],
  ['C', ['D']],
  ['D', []],
]);
breadthFirstSearch(g1, 'A'); // → ['A', 'B', 'C', 'D']

// Branching, with a shared descendant. BFS visits by level:
//   A
//  / \
// B   C
//  \ / \
//   D   E
const g2 = new Map([
  ['A', ['B', 'C']],
  ['B', ['D']],
  ['C', ['D', 'E']],
  ['D', []],
  ['E', []],
]);
breadthFirstSearch(g2, 'A'); // → ['A', 'B', 'C', 'D', 'E']

// Cycle: A → B → C → A. BFS must not loop forever.
const g3 = new Map([
  ['A', ['B']],
  ['B', ['C']],
  ['C', ['A']],
]);
breadthFirstSearch(g3, 'A'); // → ['A', 'B', 'C']

Notes

• Order matters — within a level, visit neighbors in the order they appear in the adjacency list. Tests are deterministic.
• No revisits — a node appears in the output at most once, even if many paths lead to it.
• Unreachable nodes are not included — BFS from A returns only what's reachable from A. Disconnected components are skipped.
• The start vertex is always in the output (assuming it exists in the graph), even when it has zero out-neighbors.
• Don't worry about weighted edges, shortest-path reconstruction, or undirected graphs — this is pure visit-order BFS on a directed adjacency list.