Breadth-First Search - JavaScript DSA

From a start vertex, explore the graph layer by layer. Use a queue and a "visited" set. Dequeue a vertex, visit it, enqueue all unvisited neighbours.

Algorithm

Canonical adjacency list:

1 -> [2, 3]
2 -> [1, 4]
3 -> [1, 4]
4 -> [2, 3, 5]
5 -> [4, 6]
6 -> [5]

Starting at vertex 1, the BFS visit order is [1, 2, 3, 4, 5, 6].

Basic Implementation

basic.js

const adj = new Map();
adj.set(1, [2, 3]);
adj.set(2, [1, 4]);
adj.set(3, [1, 4]);
adj.set(4, [2, 3, 5]);
adj.set(5, [4, 6]);
adj.set(6, [5]);

const start = 1;
const visited = new Set([start]);
const queue = [start];
const order = [];
while (queue.length > 0) {
    const v = queue.shift();
    order.push(v);
    for (const nb of adj.get(v)) {
        if (!visited.has(nb)) {
            visited.add(nb);
            queue.push(nb);
        }
    }
}
console.log(JSON.stringify(order));

Complexity

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

Implementation notes

JavaScript: use new Map() for the adjacency list so insertion order is preserved, matching the lesson spec's deterministic neighbour order. array.shift() keeps the BFS pattern obvious at the cost of O(n) dequeue — fine for the canonical small input.
The replay prints the dequeued vertex, the queue, the visited set, and the running visit order each frame.

queue A plain array doubles as a FIFO queue: `push` to enqueue, `shift` to dequeue.

visited-before-enqueue Mark a vertex visited before pushing it onto the queue. Keeps the queue size bounded by V.