BFS Graph Traversal

The problem

Implement `bfs(graph, source)` where `graph` is an adjacency list (`{ node: [neighbours] }`) and `source` is the starting node. Return an array of every node reachable from `source`, in breadth-first order.

For `{ a: ['b', 'c'], b: ['d'], c: ['e'], d: [], e: [] }` starting at `a`, the expected order is `['a', 'b', 'c', 'd', 'e']` — both of `a`'s direct neighbours come out before either of theirs. It also has to cope with disconnected nodes (nodes with no path from `source` just don't appear) and single-node graphs.

The approach

A queue is the whole trick: `q = [source]`, then loop while it's non-empty, `shift()` the front node off, record it in `result`, and `push()` each of its neighbours onto the back. Because `shift()` always takes the oldest entry, every node at depth `k` is dequeued — and its neighbours enqueued — before any node at depth `k+1` gets touched.

There's no visited set here because the test graphs are all trees (each node has exactly one path in from `source`), so nothing gets revisited. On a graph with cycles or shared neighbours this would need a `visited` `Set` checked before pushing, or the same node could be queued twice and `result` would contain duplicates.

The solution

export function bfs(graph, source) {
    const q = [source]
    const result = []
    while (q.length) {
        const node = q.shift()
        result.push(node)
        for (let neighbour of graph[node]) {
            q.push(neighbour)
        }
    }
    return result
}

Time O(V + E)Space O(V)