Breadth First Search - A Complete Guide

Breadth-first search (BFS) is a fundamental algorithm used for traversing or searching tree and graph data structures. Unlike its counterpart depth-first search (DFS), BFS explores data structures level by level, making it particularly useful for finding the shortest path in unweighted graphs or exploring nodes in order of their distance from the starting point.

The algorithm begins at the tree root (or an arbitrary node in a graph, often called the ‘search key’) and systematically explores all neighboring nodes at the current depth level before advancing to nodes at the next depth level. This layer-by-layer exploration strategy gives BFS its characteristic “breadth-first” behavior.

Key Characteristics of BFS #

BFS has several important properties that make it valuable for specific applications:

Complete: BFS will always find a solution if one exists, as it systematically explores every node.

Optimal for Unweighted Graphs: When all edges have equal weight, BFS guarantees finding the shortest path between two nodes.

Memory Intensive: BFS typically requires more memory than DFS because it must store all nodes at the current level before moving to the next level.

Level-Order Traversal: BFS naturally performs a level-order traversal, which is useful for many tree-related problems.

Tree Structure Implementation #

Before diving into the BFS algorithm, let’s establish our tree data structure. See the page on trees for a comprehensive example of tree implementation in JavaScript.

function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

This simple Node constructor creates a binary tree node with a value and pointers to left and right children. This structure forms the foundation for our BFS implementation.

Understanding the BFS Algorithm #

The core strategy behind BFS is relatively straightforward, but understanding its mechanics is crucial for proper implementation. Unlike depth-first search which uses recursion or a stack, BFS relies on a queue data structure to maintain the order of exploration.

The algorithm follows these steps:

  1. Start at the Root Node: Begin at the root of the tree or an arbitrary starting node in a graph.

  2. Process the Current Level: Examine all nodes at the current depth level, adding their children to a queue for later processing.

  3. Move to the Next Level: Once all nodes at the current level are processed, move to the next level by processing nodes from the queue.

  4. Track Visited Nodes (For Graphs): When working with graphs, maintain a record of visited nodes to avoid infinite loops caused by cycles.

  5. Continue Until Complete: Repeat this process until all reachable nodes have been visited or the target node is found.

Why Not Use Recursion for BFS? #

An important distinction between BFS and DFS is that recursion is not the natural approach for BFS. While recursion works elegantly for DFS due to the call stack’s LIFO (Last In, First Out) nature matching DFS’s exploration pattern, BFS requires FIFO (First In, First Out) behavior.

You could theoretically implement BFS recursively by passing the queue as a parameter and recursively calling the function for each level, but this approach is awkward, less efficient, and goes against the natural iterative flow of BFS. The iterative approach using a queue is cleaner, more intuitive, and performs better.

BFS Iterative Implementation - Binary Tree #

The iterative approach is the standard and most efficient way to implement BFS. Here’s a corrected and improved implementation in JavaScript:

function BFS(node) {
  if (!node) return; // Handle empty tree
  
  let queue = [node]; // FIFO: First In, First Out
  
  while (queue.length > 0) { // While queue isn't empty
    const current = queue.shift(); // Remove and get first item from queue
    
    // Process current node
    console.log(current.value);
    
    // Add children to queue (left to right order)
    if (current.left) {
      queue.push(current.left); // Add left child to end of queue
    }
    if (current.right) {
      queue.push(current.right); // Add right child to end of queue
    }
  }
}

How This Implementation Works #

The key to this implementation is the queue data structure. We use a JavaScript array and manipulate it with shift() (removes from front) and push() (adds to back) to create FIFO behavior.

Step-by-Step Execution: Imagine a tree where the root has value 1, with left child 2 and right child 3. Node 2 has children 4 and 5, while node 3 has children 6 and 7.

  1. Initial State: Queue contains [1]
  2. First Iteration: Process node 1, add nodes 2 and 3. Queue becomes [2, 3]
  3. Second Iteration: Process node 2, add nodes 4 and 5. Queue becomes [3, 4, 5]
  4. Third Iteration: Process node 3, add nodes 6 and 7. Queue becomes [4, 5, 6, 7]
  5. Subsequent Iterations: Process nodes 4, 5, 6, and 7 in order

The output would be: 1, 2, 3, 4, 5, 6, 7 - a perfect level-order traversal.

BFS for Graphs #

When implementing BFS for graphs (as opposed to trees), you need to track visited nodes to avoid infinite loops:

function BFS_Graph(startNode) {
  if (!startNode) return;
  
  let queue = [startNode];
  let visited = new Set([startNode]); // Track visited nodes
  
  while (queue.length > 0) {
    const current = queue.shift();
    
    // Process current node
    console.log(current.value);
    
    // Visit all neighbors
    for (let neighbor of current.neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

Difference Between BFS and DFS #

Understanding the distinction between BFS and DFS is crucial for choosing the right algorithm for your problem.

Data Structure: The fundamental difference lies in the data structure used:

  • BFS uses a Queue (FIFO): Children are added to the end of the queue and processed after all current-level nodes
  • DFS uses a Stack (LIFO): Children are added to the top of the stack and processed immediately before siblings

Exploration Pattern:

  • BFS explores horizontally: It visits all nodes at depth d before visiting any node at depth d+1
  • DFS explores vertically: It visits nodes by going as deep as possible down one path before backtracking

Use Cases:

  • BFS is better for: Finding shortest paths, level-order traversal, finding nodes within a certain distance, web crawling
  • DFS is better for: Detecting cycles, topological sorting, solving puzzles with one solution, using less memory when the tree is very wide

Memory Usage:

  • BFS: Requires O(w) space where w is the maximum width of the tree (can be very large for wide trees)
  • DFS: Requires O(h) space where h is the maximum height of the tree (better for wide, shallow trees)

Implementation Style:

  • BFS: Naturally iterative with a queue
  • DFS: Naturally recursive (or iterative with a stack)

Practical Applications of BFS #

BFS has numerous real-world applications:

Social Networks: Finding the shortest connection path between two people (degrees of separation)

GPS Navigation: Finding the shortest route in unweighted road networks

Web Crawlers: Systematically exploring websites level by level

Puzzle Solving: Finding the minimum number of moves to solve a puzzle (like a Rubik’s cube)

Network Broadcasting: Ensuring messages reach all nodes in a network efficiently

Peer-to-Peer Networks: Discovering nodes in distributed systems

Time and Space Complexity #

For a graph or tree with V vertices and E edges:

Time Complexity: O(V + E) - Each vertex and edge is explored once

Space Complexity: O(V) - In the worst case, the queue might need to store all vertices at one level

For a complete binary tree specifically:

  • The worst-case space complexity is O(w) where w is the width of the tree at its widest point, which occurs at the last level and equals approximately n/2 nodes.

Conclusion #

Breadth-first search is an essential algorithm in computer science, providing an efficient method for level-by-level exploration of trees and graphs. Its queue-based iterative implementation makes it perfect for finding shortest paths and exploring data structures in a systematic, ordered manner. Understanding when to use BFS versus DFS is a key skill in algorithm design and problem-solving.

Previous Breadth First Search for Graphs Jump Game: A Deep Dive into Algorithmic Solutions Next