Graphs

Breadth-First Search

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

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));

BFS uses a queue, so it visits the start vertex, then its neighbours, then the next layer.

Step 1 - Start at 1

The queue starts with [1] and visited starts with {1}.

BFS start state: queue [1], visited {1}.1#123456

Step 2 - Visit the first layer

After processing 1, neighbours 2 and 3 are marked and queued.

Queue after visiting 1: [2, 3].1#12queued3queued456

Step 3 - Deterministic visit order

With insertion-ordered neighbours, BFS visits [1, 2, 3, 4, 5, 6].

Final BFS visit order from start 1.1#12#23#34#45#56#6

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.