Breadth-First Search (BFS)

Overview

Breadth-First Search (BFS) is a fundamental graph traversal algorithm that explores all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. It is a "level-order" traversal, meaning it visits nodes layer by layer, starting from the source node.

The Core Concept

Imagine you are standing in the center of a room filled with people. You want to say hello to everyone, but you can only speak to the people immediately next to you. Once you've said hello to everyone in your immediate circle, you move to the next circle of people, and so on. This is exactly what BFS does in a graph: it expands outward from the starting node in concentric circles (levels).

Graph Representation

For BFS to be efficient, graphs are typically represented using an Adjacency List. This allows us to quickly access all neighbors of a given node.

// Adjacency List representation of a graph
const graph = new Map<number, number[]>();

graph.set(0, [1, 2]);
graph.set(1, [0, 3, 4]);
graph.set(2, [0, 5]);
graph.set(3, [1]);
graph.set(4, [1, 5]);
graph.set(5, [2, 4]);

Algorithm Steps

Initialization: Create a queue to manage the nodes to be visited and a visited set to keep track of nodes that have already been processed to avoid cycles.
Enqueue Start: Add the starting node to the queue and mark it as visited.
Process Queue: While the queue is not empty:

Dequeue: Remove the front node from the queue.
Process: Perform the desired operation on the node (e.g., print its value).
Enqueue Neighbors: Iterate through all adjacent nodes. If a neighbor hasn't been visited, add it to the queue and mark it as visited.

Implementation

Here is a TypeScript implementation of BFS:

type Graph = Map<number, number[]>;

function bfs(graph: Graph, startNode: number): number[] {
  const visited = new Set<number>();
  const queue: number[] = [startNode];
  const result: number[] = [];

  visited.add(startNode);

  while (queue.length > 0) {
    // Dequeue the front node
    const currentNode = queue.shift()!;
    result.push(currentNode);

    // Get neighbors
    const neighbors = graph.get(currentNode) || [];

    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return result;
}

// Usage
const myGraph: Graph = new Map([
  [0, [1, 2]],
  [1, [0, 3, 4]],
  [2, [0, 5]],
  [3, [1]],
  [4, [1, 5]],
  [5, [2, 4]]
]);

console.log(bfs(myGraph, 0)); // Output: [0, 1, 2, 3, 4, 5]

Complexity Analysis

Time Complexity: O(V + E)

V (Vertices): We visit each vertex exactly once.
E (Edges): We iterate through each edge exactly once (when checking neighbors).

Space Complexity: O(V)

Queue: In the worst case (a linear chain graph), the queue can hold up to V nodes.
Visited Set: We store V nodes to keep track of visited vertices.

Common Patterns and Use Cases

1. Shortest Path in Unweighted Graphs

BFS is the standard algorithm for finding the shortest path between two nodes in an unweighted graph. Since BFS explores nodes level by level, the first time we reach the target node, we have found the shortest path.

2. Level Order Traversal

This is the graph equivalent of a tree's level order traversal. It is used to analyze the structure of the graph layer by layer.

3. Cycle Detection

By maintaining a visited set, BFS can detect cycles. If we encounter a node that is already in the queue (but not yet processed), it indicates a cycle.

4. Topological Sort (Kahn's Algorithm)

BFS can be used to perform a topological sort of a directed acyclic graph (DAG) by repeatedly removing nodes with no incoming edges.

Real-World Applications

Social Networks: Finding "friends of friends" or the shortest connection path between two people (e.g., "Six Degrees of Kevin Bacon").
Web Crawling: Search engines use BFS to index web pages, starting from a seed URL and following links to discover new pages.
GPS Navigation: Finding the shortest route between two locations in a city where all roads have equal weight.
Broadcasting: Sending a message to all connected nodes in a network simultaneously.

Common Mistakes to Avoid

Forgetting the Visited Set: This is the most common error. Without a visited set, an algorithm will get stuck in an infinite loop if the graph contains cycles.
Using a Stack (DFS) instead of a Queue: BFS relies on a First-In-First-Out (FIFO) structure. Using a Stack (Last-In-First-Out) will result in a Depth-First Search (DFS).
Not Handling Disconnected Graphs: If the graph is disconnected, a simple BFS from a single start node will only visit the connected component containing that node. You must run BFS for every unvisited node to cover the entire graph.

Summary

Breadth-First Search is a versatile algorithm that trades depth for breadth. It is the go-to choice when you need to find the shortest path in an unweighted graph or when you need to process nodes level by level. Understanding the Queue data structure and the Adjacency List representation is crucial for mastering BFS.

Breadth-First Search (BFS) - Complete Guide