Breadth-First Search for Shortest Paths

Welcome back! In our last lesson, we laid the groundwork for working with graphs by learning how to represent them in code using adjacency lists. We now have a solid way to model networks and relationships. The natural next question is: what can we do with these structures?

Today, we'll learn our first fundamental graph algorithm: Breadth-First Search (BFS). This is more than just a way to visit every node; it’s a powerful technique that explores a graph in a very specific order—layer by layer. This property makes it the perfect tool for finding the shortest path between two nodes in an unweighted graph. By the end of this lesson, you will be able to implement BFS to systematically find and record the shortest distances from a starting node to all other reachable nodes.

The Core Idea: Exploring in Waves

Before we touch any code, let's build an intuition for how BFS works. Imagine dropping a pebble into a calm pond. Ripples expand outwards in concentric circles. The first ripple touches everything one unit away, the second ripple touches everything two units away, and so on.

BFS explores a graph in exactly the same way. Starting from a source node, it first visits all the immediate neighbors (one edge away). Then, it visits all of their neighbors (two edges away), and continues this process, exploring the graph in "layers" of increasing distance.

This layer-by-layer approach is the key to its power. Because BFS always explores all nodes at a distance $d$ before moving on to nodes at distance $d+1$, the first time it reaches any node, it is guaranteed to have found a shortest path to it, measured by the number of edges.

This works perfectly for unweighted graphs, where every edge has the same "cost" of 1. However, it's important to recognize that this simple BFS approach does not work for weighted graphs, where edges have different costs. The image below illustrates this critical distinction.

For the rest of this lesson, we'll focus on unweighted graphs, where BFS shines.

The Algorithm: How a Queue Creates the Waves

To implement this "expanding wave" exploration, we need a data structure that processes nodes in the order they are discovered. This is a perfect use case for a Queue (First-In, First-Out).

Professor Mary Elaine Califf's video provides a great conceptual introduction. Please watch the first part where she explains the idea of exploring layer-by-layer and lists the data structures we'll need.

As the video explains, the core algorithm looks like this:

1. Initialize:
   • Create a queue and add the start node to it.
   • Create a distances data structure (like a Map or an object) to store the shortest distance from the start node to every other node. Initialize the distance to the start node as 0 and all others as infinity. This map also serves to track visited nodes.
2. Loop:
   • While the queue is not empty:
     • Dequeue the current node.
     • For each of its neighbors:
       • If the neighbor has not been visited (i.e., its distance is still infinity):
         • Update its distance: distance[neighbor] = distance[current] + 1.
         • Enqueue the neighbor.

A Step-by-Step Walkthrough

Let's trace this process on an example. The following video from the "take U forward" channel gives an exceptionally clear, step-by-step visualization of how the queue and the distance array are updated during a BFS traversal.

The key takeaway from the video is that the distances array (or map) is not just for storing the final result; it's also our "visited" tracker. If distances[node] is anything other than infinity, we've already found a path to it. Since BFS explores layer by layer, we know that the first path we find is the shortest, so we never need to update the distance for an already-visited node.

Here is the graph from the video, showing the final shortest distances from the source node 0. Your BFS implementation will produce these values.

Implementing BFS in TypeScript

Now, let's translate this logic into code. We'll write a function that takes a graph's adjacency list, a start node, and computes the distances to all other nodes.

A common and clean pattern is to store pairs of [node, distance] in the queue. This avoids looking up the current node's distance in every iteration of the loop.

function bfsShortestPath<T extends string | number>(
    adjacencyList: Map<T, Set<T>>,
    startNode: T
): Map<T, number> {
    // 1. Initialize distances
    const distances = new Map<T, number>();
    for (const vertex of adjacencyList.keys()) {
        distances.set(vertex, Infinity);
    }
    distances.set(startNode, 0);

    // 2. Initialize the queue
    const queue: [T, number][] = [[startNode, 0]];
    
    // We'll use a head index for an efficient queue
    let head = 0;

    // 3. Loop until the queue is empty
    while (head < queue.length) {
        const [currentNode, currentDistance] = queue[head];
        head++;

        // 4. Process neighbors
        const neighbors = adjacencyList.get(currentNode) || new Set();
        for (const neighbor of neighbors) {
            if (distances.get(neighbor) === Infinity) { // If not visited
                distances.set(neighbor, currentDistance + 1);
                queue.push([neighbor, currentDistance + 1]);
            }
        }
    }

    return distances;
}

// Example usage:
const edges = [
    [0, 1], [0, 3],
    [1, 7],
    [3, 2], [3, 4],
    [2, 7], [2, 5],
    [5, 6],
    [8, 0] // Node 8 is also connected to 0
];
const adjList = new Map<number, Set<number>>();
edges.forEach(([u, v]) => {
    if (!adjList.has(u)) adjList.set(u, new Set());
    if (!adjList.has(v)) adjList.set(v, new Set());
    adjList.get(u)!.add(v);
    adjList.get(v)!.add(u);
});

// A node that is not in the edges list
adjList.set(9, new Set());

const shortestDistances = bfsShortestPath(adjList, 0);
console.log(shortestDistances);
/*
Map {
  0 => 0,
  1 => 1,
  3 => 1,
  8 => 1,
  7 => 2,
  2 => 2,
  4 => 2,
  5 => 3,
  6 => 4,
  9 => Infinity // Unreachable
}
*/

A Critical Performance Note for JavaScript/TypeScript

In the code above, notice we used let head = 0; and head++ to simulate a queue, rather than using Array.prototype.shift(). This is a vital optimization. In JavaScript, shift() is an O(n) operation because it requires re-indexing all subsequent elements in the array. For a large graph, this can turn your efficient O(V+E) BFS into a much slower algorithm.

The blog post "Breadth First Search in JavaScript" explains this problem and presents a proper queue implementation. For interview readiness, this is a crucial detail to master.

Another Implementation Perspective

There are several slightly different ways to structure the BFS code. The article "Shortest Path Algorithm in Unweighted Graph Using BFS" presents a "layer-by-layer" implementation that uses two arrays to keep track of the current and next layers of nodes. It's a useful alternative to see.

Conclusion

Today you've added a cornerstone algorithm to your toolkit. Breadth-First Search is not just for traversing graphs; its fundamental layer-by-layer exploration provides a robust and efficient way to find the shortest path in any unweighted network.

Key Takeaways:

• BFS explores graphs in expanding layers from a source node, using a queue to manage the order of visitation.
• This property guarantees that the first time BFS reaches a node, it does so via a shortest path in an unweighted graph.
• To record distances, we use a distances map, initializing the start node to 0 and all others to Infinity. A node's distance is set to distance[parent] + 1 when it's first discovered.
• In JavaScript/TypeScript, avoid Array.prototype.shift() in your queue implementation for BFS to maintain optimal performance. Use a custom queue or a pointer-based approach with a plain array.

In our next lesson, we will explore the other fundamental graph traversal algorithm: Depth-First Search (DFS). We will see how its recursive, path-deepening nature, implemented with a stack (often the implicit call stack), solves a different class of problems, such as cycle detection and exploring mazes.