Breadth-First Search: Complete Graph Traversal Guide

Master BFS algorithm for level-order traversal, shortest path finding, and connected components. This tutorial covers iterative and recursive implementations, complexity analysis, and real-world applications with coding examples.

BFS Usage in Applications (2023)

Shortest Path (30%)

Social Networks (25%)

Web Crawling (20%)

Puzzle Solving (15%)

Other (10%)

1. BFS Fundamentals

Core Properties:

Level-Order Traversal: Visits nodes level by level
Queue-Based: Uses FIFO queue for exploration
Shortest Path: Finds minimal path in unweighted graphs
Complete: Visits all reachable nodes

Time Complexities:

Scenario	Time	Space
Adjacency List	O(V + E)	O(V)
Adjacency Matrix	O(V²)	O(V)
Tree Traversal	O(N)	O(W)
Grid Traversal	O(R×C)	O(R×C)

BFS Implementation:

Graph BFS (Adjacency List)


function bfs(start) {
  const queue = [start];
  const visited = new Set([start]);
  const result = [];
  
  while (queue.length > 0) {
    const vertex = queue.shift();
    result.push(vertex);
    
    for (const neighbor of this.adjList.get(vertex)) {
      if (!visited.has(neighbor.node)) {
        visited.add(neighbor.node);
        queue.push(neighbor.node);
      }
    }
  }
  return result;
}

Tree BFS (Level Order)


function levelOrder(root) {
  if (!root) return [];
  const queue = [root];
  const result = [];
  
  while (queue.length) {
    const levelSize = queue.length;
    const currentLevel = [];
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    
    result.push(currentLevel);
  }
  return result;
}

2. BFS Variations & Applications

Algorithm Variations:

Multi-Source BFS

For multiple starting points


function multiSourceBFS(sources) {
  const queue = [...sources];
  const visited = new Set(sources);
  const distances = new Map();
  sources.forEach(src => distances.set(src, 0));
  
  while (queue.length) {
    const current = queue.shift();
    
    for (const neighbor of getNeighbors(current)) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        distances.set(neighbor, distances.get(current) + 1);
        queue.push(neighbor);
      }
    }
  }
  return distances;
}

Bidirectional BFS

Search from both ends


function bidirectionalBFS(start, end) {
  let startQueue = [start], endQueue = [end];
  const startVisited = new Set([start]);
  const endVisited = new Set([end]);
  let steps = 0;
  
  while (startQueue.length && endQueue.length) {
    // Expand from start
    let size = startQueue.length;
    for (let i = 0; i < size; i++) {
      const node = startQueue.shift();
      if (endVisited.has(node)) return steps;
      // Process neighbors...
    }
    steps++;
    
    // Expand from end
    size = endQueue.length;
    for (let i = 0; i < size; i++) {
      const node = endQueue.shift();
      if (startVisited.has(node)) return steps;
      // Process neighbors...
    }
    steps++;
  }
  return -1; // No path
}

Real-world Applications:

Social Networking: Friend recommendation systems (3rd degree connections)
GPS Navigation: Shortest route finding in road networks
Web Crawling: Indexing web pages level by level
Puzzle Solving: Rubik's cube solution finder
Network Broadcasting: Packet routing in computer networks

3. BFS Problem Patterns

Common Problem Types:

Shortest Path in Grid


function shortestPathBinaryMatrix(grid) {
  if (grid[0][0] === 1) return -1;
  const n = grid.length;
  const queue = [[0, 0, 1]]; // [row, col, distance]
  const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],
                [0,1],[1,-1],[1,0],[1,1]];
  
  while (queue.length) {
    const [r, c, dist] = queue.shift();
    if (r === n-1 && c === n-1) return dist;
    
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < n && nc >= 0 && nc < n 
          && grid[nr][nc] === 0) {
        grid[nr][nc] = 1; // Mark visited
        queue.push([nr, nc, dist + 1]);
      }
    }
  }
  return -1;
}

Word Ladder


function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  
  const queue = [beginWord];
  let level = 1;
  
  while (queue.length) {
    const levelSize = queue.length;
    for (let i = 0; i < levelSize; i++) {
      const current = queue.shift();
      if (current === endWord) return level;
      
      for (let j = 0; j < current.length; j++) {
        for (let c = 97; c <= 122; c++) {
          const next = current.slice(0, j) + 
                      String.fromCharCode(c) + 
                      current.slice(j+1);
          if (wordSet.has(next)) {
            queue.push(next);
            wordSet.delete(next);
          }
        }
      }
    }
    level++;
  }
  return 0;
}

Optimization Techniques:

Early Termination: Stop when target is found
Visited Tracking: Prevent redundant processing
Level Tracking: Maintain distance information
Dual-direction Search: Bidirectional BFS for large graphs
Priority Queues: For weighted graph variations

BFS Problem-Solving Cheat Sheet

Problem Type	Key Insight	Time Complexity
Shortest Path (Unweighted)	First encounter is shortest	O(V + E)
Connected Components	Complete traversal from source	O(V + E)
Bipartite Check	Alternating level coloring	O(V + E)
Topological Sort	Kahn's algorithm (modified BFS)	O(V + E)
Word Ladder	Implicit graph construction	O(N×L²)

4. Advanced BFS Concepts

0-1 BFS

For graphs with 0/1 weights


function zeroOneBFS(start) {
  const dist = Array(n).fill(Infinity);
  const deque = [start];
  dist[start] = 0;
  
  while (deque.length) {
    const u = deque.shift();
    
    for (const [v, weight] of adj[u]) {
      if (dist[v] > dist[u] + weight) {
        dist[v] = dist[u] + weight;
        if (weight === 0) deque.unshift(v);
        else deque.push(v);
      }
    }
  }
  return dist;
}

BFS with State

Tracking additional information


function shortestPathWithKeys(grid) {
  const m = grid.length, n = grid[0].length;
  const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
  const queue = []; // [row, col, keyState]
  const visited = new Set();
  
  // Find starting position
  // Initialize queue and visited
  
  while (queue.length) {
    const [r, c, keys] = queue.shift();
    if (grid[r][c] === 'T') return steps;
    
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      const newKeys = updateKeys(keys, grid[nr][nc]);
      const state = `${nr},${nc},${newKeys}`;
      
      if (isValid(nr, nc, newKeys) && !visited.has(state)) {
        visited.add(state);
        queue.push([nr, nc, newKeys, steps + 1]);
      }
    }
  }
  return -1;
}

Parallel BFS

For multi-core processing


// Conceptual implementation
async function parallelBFS(start, numWorkers = 4) {
  const globalQueue = new SharedQueue([start]);
  const visited = new SharedSet([start]);
  const workers = [];
  
  for (let i = 0; i < numWorkers; i++) {
    workers.push(workerProcess(globalQueue, visited));
  }
  
  await Promise.all(workers);
  return visited.getValues();
}

// Worker would process a chunk of nodes
// and synchronize through shared structures

BFS Problem-Solving Checklist

✓ Identify level-order or shortest path requirements

✓ Choose appropriate data structure (queue/deque)

✓ Track visited states to prevent cycles

✓ Consider bidirectional search for large graphs

✓ Optimize with early termination when possible

DSA Expert Insight: BFS appears in 25% of graph-related interview questions. Mastering its variations (multi-source, bidirectional, 0-1) can help solve complex traversal problems efficiently. Remember that BFS naturally finds the shortest path in unweighted graphs.

0 Interaction

0 Views

0 Likes