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

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

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.