Breadth First Search for Graphs

Introduction #

This article provides a detailed explanation of how to implement Breadth First Search (BFS) for graphs in JavaScript. While BFS shares conceptual similarities with its tree-based counterpart, the graph implementation requires special considerations to handle cyclic structures and multiple connection paths. For information on Depth First Search or the tree-based implementation of BFS, please refer to the main BFS article.

Understanding BFS for Graphs #

Breadth First Search is a fundamental graph traversal algorithm that explores vertices in layers, visiting all immediate neighbors before moving to the next level of depth. Unlike trees, graphs can contain cycles and multiple paths between nodes, which introduces unique challenges that must be addressed in the implementation.

Key Differences from Tree BFS #

When implementing BFS for graphs versus trees, several important distinctions emerge:

  1. No hierarchical structure: Graphs don’t have a clear parent-child relationship or left-right branches like binary trees do
  2. Cycle detection: Graphs may contain cycles, requiring us to track visited nodes to prevent infinite loops
  3. Multiple paths: A single node can be reached through multiple paths, making visited tracking essential
  4. Bidirectional edges: Edges in graphs can be directed or undirected, affecting how we traverse neighbors

Algorithm Strategy #

The core strategy for BFS in graphs follows a systematic approach that ensures we visit each node exactly once while exploring the graph level by level. Here’s the step-by-step process:

  1. Dequeue operation: Remove the next item from the front of the queue (FIFO - First In, First Out)
  2. Process the node: Perform whatever operation is needed on the current node (printing, searching, etc.)
  3. Explore neighbors: For each adjacent node connected to the current node:
    • Check if the neighbor has already been visited
    • If not visited, mark it as visited to prevent revisiting
    • Add the unvisited neighbor to the end of the queue for future processing

This approach guarantees that we explore the graph in breadth-first order, visiting all nodes at distance k before visiting any nodes at distance k+1 from the starting node.

JavaScript Implementation #

Here’s a corrected and improved implementation of BFS for graphs in JavaScript:

// Adjacency list representation of the graph
// adj[i] contains an array of all nodes connected to node i
let adj;

/**
 * Performs Breadth First Search starting from the given node
 * @param {number} startNode - The starting node for BFS traversal
 */
function BFS(startNode) {
  // Initialize queue with starting node (FIFO: First In, First Out)
  let queue = [startNode];
  
  // Track visited nodes to prevent cycles and redundant processing
  let visited = new Set();
  visited.add(startNode);

  while (queue.length > 0) {
    // Dequeue: take from the front of the queue (first item)
    const current = queue.shift();

    // Process current node (customize this based on your needs)
    console.log(current);

    // Explore all neighbors of the current node
    for (let i = 0; i < adj[current].length; i++) {
      const neighbor = adj[current][i];
      
      // Only process unvisited neighbors
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

Code Improvements Explained #

The improved implementation includes several important fixes and enhancements:

1. Correct Neighbor Access #

The original code had a bug where it checked visited[current] instead of visited[neighbor]. The corrected version properly stores the neighbor in a variable and checks if that specific neighbor has been visited.

2. Using Set for Visited Tracking #

Instead of an array, the implementation now uses a Set for the visited list. This provides O(1) lookup time instead of O(n), significantly improving performance for large graphs.

3. Mark as Visited Before Enqueuing #

Nodes are now marked as visited immediately when added to the queue, not when dequeued. This prevents the same node from being added to the queue multiple times if it has multiple incoming edges.

4. Better Variable Naming #

The code uses startNode and neighbor for clarity, making the algorithm easier to understand and maintain.

Complete Example with Graph Setup #

Here’s a full working example that includes graph construction:

/**
 * Example graph represented as an adjacency list
 * Graph structure:
 *     0
 *    / \
 *   1   2
 *  / \   \
 * 3   4   5
 */
let adj = [
  [1, 2],    // Node 0 connects to nodes 1 and 2
  [0, 3, 4], // Node 1 connects to nodes 0, 3, and 4
  [0, 5],    // Node 2 connects to nodes 0 and 5
  [1],       // Node 3 connects to node 1
  [1],       // Node 4 connects to node 1
  [2]        // Node 5 connects to node 2
];

function BFS(startNode) {
  let queue = [startNode];
  let visited = new Set();
  visited.add(startNode);

  console.log("BFS Traversal Order:");
  
  while (queue.length > 0) {
    const current = queue.shift();
    console.log(`Visiting node: ${current}`);

    for (let i = 0; i < adj[current].length; i++) {
      const neighbor = adj[current][i];
      
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

// Execute BFS starting from node 0
BFS(0);
// Output: Visiting node: 0, 1, 2, 3, 4, 5

Time and Space Complexity #

Understanding the performance characteristics of BFS is crucial for choosing the right algorithm:

  • Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges. We visit each vertex once and explore each edge once.
  • Space Complexity: O(V) for storing the queue and visited set. In the worst case, the queue might contain all vertices at the same level.

Common Use Cases #

BFS for graphs is particularly well-suited for several practical applications:

  1. Shortest path finding: In unweighted graphs, BFS finds the shortest path between two nodes
  2. Social network analysis: Finding degrees of separation between people (like “Six Degrees of Kevin Bacon”)
  3. Web crawling: Systematically exploring websites level by level
  4. Network broadcasting: Determining how information spreads through a network
  5. Puzzle solving: Finding the minimum number of moves to solve puzzles like Rubik’s Cube
  6. GPS navigation: Finding routes in road networks when all edges have equal weight

Conclusion #

Breadth First Search is a powerful and versatile graph traversal algorithm that forms the foundation for many advanced graph algorithms. The key to implementing BFS correctly for graphs lies in proper visited node tracking to handle cycles and multiple paths. By using a queue data structure and maintaining a visited set, we ensure efficient and correct traversal of any graph structure. Understanding BFS deeply will serve as a springboard for learning more complex graph algorithms like Dijkstra’s shortest path and various network flow algorithms.

Previous Master Computer Science Algorithms Breadth First Search - A Complete Guide Next