Breadth-First Search - TypeScript 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

Basic Implementation

basic.ts

const adj: Map<number, number[]> = 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: number = 1;
const visited: Set<number> = new Set([start]);
const queue: number[] = [start];
const order: number[] = [];
while (queue.length > 0) {
    const v: number = queue.shift() as number;
    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}.

Step 2 - Visit the first layer

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

Step 3 - Deterministic visit order

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

Complexity

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

Implementation notes

TypeScript: use Map<number, number[]> 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.
Set<number> documents the visited-set contract; the as number cast on queue.shift() acknowledges the loop-guard invariant.
The replay prints the dequeued vertex, the queue, the visited set, and the running visit order each frame.

queue A plain `number[]` 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.