Views

Report Content

×

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.

Share and Join the Discussion

You need to be logged in to participate in this discussion.

×
×