Graph BFS

Concept

Breadth-First Search (BFS) explores the graph horizontally. It visits the Starting Node (Distance 0). Then it visits all immediate neighbors (Distance 1). Then it visits all neighbors’ neighbors (Distance 2).

This outward “ripple” effect gives BFS its mathematical superpower: The very first time BFS encounters a target node, it is absolutely guaranteed to be the shortest path to that node.

Just like Tree BFS, we use a Queue to manage the order.
Just like Graph DFS, we must use a Visited Set to prevent infinite loops.

Implementation

// Time Complexity: O(V + E)
// Space Complexity: O(V) (Queue + Visited Set)

function graphBFS(startNode: number, adjList: Map<number, number[]>) {
    const queue: number[] = [startNode];
    const visited = new Set<number>();
    
    // CRITICAL: Mark as visited the instant it enters the queue!
    visited.add(startNode);
    
    let distance = 0; // Tracks the radius of the ripple

    while (queue.length > 0) {
        // Snapshot the current level size
        const levelSize = queue.length;
        
        // Process all nodes at this exact distance
        for (let i = 0; i < levelSize; i++) {
            const current = queue.shift()!;
            
            console.log(`Visiting Node ${current} at Distance ${distance}`);
            
            const neighbors = adjList.get(current) || [];
            for (let neighbor of neighbors) {
                // If we haven't seen it yet...
                if (!visited.has(neighbor)) {
                    // Mark it visited NOW, before it even gets processed
                    visited.add(neighbor);
                    queue.push(neighbor);
                }
            }
        }
        
        // After processing everyone at the current radius, increment the distance
        distance++;
    }
}

The “Visited” Timing Trap

Notice the comment: CRITICAL: Mark as visited the instant it enters the queue!

In DFS, we mark a node as visited at the very top of the function (if (visited.has(node)) return; visited.add(node);).

In BFS, a common beginner mistake is to push neighbors into the queue, and then mark them as visited later when they are finally dequeued:

// BAD BFS IMPLEMENTATION:
const current = queue.shift();
visited.add(current); // Marking visited too late!

Why is this a catastrophic bug?
Imagine a dense graph where Node A, B, and C all point to Node Z.

1. Node A sees neighbor Z. Pushes Z into Queue.
2. Node B sees neighbor Z. Because Z hasn’t been officially dequeued and marked visited yet, B pushes another Z into Queue.
3. Node C sees Z. Pushes a third Z into Queue.

Node Z will be processed 3 times! In a massive graph, this causes exponential queue duplication and will completely crash your algorithm (Memory Limit Exceeded).
You must add nodes to the visited Set the exact millisecond they are .push()ed into the Queue.

Topological Sort

There is a highly advanced Graph algorithm called Topological Sort (Kahn’s Algorithm), commonly tested in the famous “Course Schedule” problem (LeetCode 207).

Problem: You have 5 college courses. Course B requires Course A. Course C requires Course B. Can you finish all courses?

This is modeled as a Directed Graph. You must process the nodes in an order that respects the dependencies.
Kahn’s Algorithm uses a highly modified BFS:

1. Calculate the In-Degree (number of incoming arrows) for every node.
2. If a node has an In-Degree of 0 (it has no prerequisites), it is safe to take! Push it into the Queue.
3. Dequeue the node. You finished the course! Now, look at all its neighbors (courses that depended on it) and reduce their In-Degree by 1.
4. If any neighbor’s In-Degree hits 0, push it into the Queue!
5. If the Queue empties, but you haven’t taken all $N$ courses, it proves there is a cycle (a deadlock) in the prerequisites.

Interview Questions

Q: You need to find the shortest path between two users in a social network. Which is faster: standard BFS, or Bidirectional BFS?
A: Bidirectional BFS is exponentially faster.
Standard BFS starting from User A will ripple outward in a massive circle ($O(B^D)$ where B is the branching factor/friends, and D is the distance).
Bidirectional BFS starts one ripple from User A, and simultaneously starts a second ripple from User Z. When the two expanding circles collide in the middle, the shortest path is found! This cuts the search depth exactly in half, completely eliminating the explosive massive outer rings of the search radius.