Traversing Graphs with BFS

1. Understanding Graph BFS

Breadth-First Search (BFS) is a graph traversal algorithm that explores nodes level by level, starting from a given source node. It uses a queue to manage the order of exploration.

Property	Description	Notes
Time Complexity	O(V + E)	V = vertices, E = edges
Space Complexity	O(V)	For the queue and visited set
Traversal Order	Level-by-level	Explores all neighbors before moving to next level
Use Case	Shortest path in unweighted graphs	Can find shortest path between nodes

Example: BFS Implementation in JavaScript

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  const result = [];

  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return result;
}

Note: BFS guarantees the shortest path in unweighted graphs. For weighted graphs, Dijkstra's algorithm is preferred.

2. Implementing Level-wise BFS

Example: BFS Traversal with Level Tracking

const graph = {
  'A': ['B', 'C'],
  'B': ['D', 'E'],
  'C': ['F'],
  'D': [],
  'E': ['G'],
  'F': [],
  'G': []
};

function bfsLevelwise(startNode) {
  const queue = [[startNode, 0]]; // [node, level]
  const visited = new Set();
  const levels = [];

  while (queue.length > 0) {
    const [node, level] = queue.shift();

    if (visited.has(node)) continue;
    visited.add(node);

    // Ensure levels array has enough slots
    if (levels.length <= level) {
      levels.push([]);
    }
    levels[level].push(node);

    // Add neighbors to queue with next level
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        queue.push([neighbor, level + 1]);
      }
    }
  }

  return levels;
}

console.log(bfsLevelwise('A'));
// Output: [['A'], ['B', 'C'], ['D', 'E', 'F'], ['G']]

Component	Description	Usage
Queue	Used to process nodes level by level	Enqueue neighbors, Dequeue current node
Visited Set	Tracks already visited nodes to prevent cycles	Add node when first encountered
Levels Array	Stores nodes grouped by their level in BFS traversal	Initialize with empty arrays for each new level

Note: The levels array is dynamically extended to accommodate new levels as they are discovered during traversal.

3. Finding Shortest Path

Property	Description	Notes
BFS Algorithm	Traverses graph level-by-level to find shortest path in unweighted graphs	Uses queue data structure for traversal
Time Complexity	O(V + E)	V = vertices, E = edges
Space Complexity	O(V)	For queue and visited set

Example: BFS Shortest Path in Grid

const shortestPathBinaryMatrix = (grid) => {
  const n = grid.length;
  if (grid[0][0] === 1 || grid[n-1][n-1] === 1) return -1;

  const queue = [[0, 0, 1]]; // [row, col, distance]
  const visited = new Set();
  visited.add("0,0");

  const directions = [[-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1]];

  while (queue.length > 0) {
    const [row, col, dist] = queue.shift();
    
    if (row === n-1 && col === n-1) return dist;

    for (const [dr, dc] of directions) {
      const newRow = row + dr;
      const newCol = col + dc;
      const key = `${newRow},${newCol}`;
      
      if (newRow >= 0 && newRow < n &&
          newCol >= 0 && newCol < n &&
          !visited.has(key) &&
          grid[newRow][newCol] === 0) {
        visited.add(key);
        queue.push([newRow, newCol, dist + 1]);
      }
    }
  }

  return -1;
};

Note: BFS guarantees the shortest path in unweighted graphs. For weighted graphs, Dijkstra's algorithm is preferred.

4. Implementing Multi-source BFS

Feature	Description	Code Example
Initialization	Start BFS from multiple sources simultaneously	`const queue = new Queue();\nconst visited = new Set();\n\n// Add all sources to queue and mark as visited\nsources.forEach(source => {\n queue.enqueue(source);\n visited.add(source);\n});`
Traversal Logic	Process nodes level by level from all sources	`while (!queue.isEmpty()) {\n const current = queue.dequeue();\n \n // Process neighbors\n for (const neighbor of getNeighbors(current)) {\n if (!visited.has(neighbor)) {\n visited.add(neighbor);\n queue.enqueue(neighbor);\n }\n }\n}`

Example: Multi-source BFS for Shortest Distance

const multiSourceBFS = (graph, sources) => {\n  const distances = new Map();\n  const queue = [];\n  \n  // Initialize sources with distance 0\n  sources.forEach(source => {\n    distances.set(source, 0);\n    queue.push(source);\n  });\n  \n  while (queue.length > 0) {\n    const node = queue.shift();\n    const currentDistance = distances.get(node);\n    \n    // Visit neighbors\n    for (const neighbor of graph[node] || []) {\n      if (!distances.has(neighbor)) {\n        distances.set(neighbor, currentDistance + 1);\n        queue.push(neighbor);\n      }\n    }\n  }\n  \n  return distances;\n};

5. Solving Rotting Oranges Problem

The Rotting Oranges problem involves determining the minimum time required for all oranges in a grid to rot, using a BFS traversal approach.

Property	Description	Value
Grid Representation	2D grid where each cell can be:	`0` (empty), `1` (fresh orange), `2` (rotten orange)
Time Calculation	Each minute, fresh oranges adjacent to rotten oranges rot	Time increases by 1 for each BFS level
Edge Cases	Return `-1` if any fresh oranges remain unrotted	Return `0` if no fresh oranges exist initially

Example: Rotting Oranges

const orangesRotting = (grid) => {
  const rows = grid.length;
  const cols = grid[0].length;
  const queue = [];
  let freshCount = 0;

  // Initialize queue with rotten oranges and count fresh
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 2) queue.push([i, j]);
      if (grid[i][j] === 1) freshCount++;
    }
  }

  const directions = [[-1,0], [1,0], [0,-1], [0,1]];
  let minutes = 0;

  while (queue.length > 0) {
    const size = queue.length;
    let rotted = false;

    for (let i = 0; i < size; i++) {
      const [r, c] = queue.shift();
      for (const [dr, dc] of directions) {
        const nr = r + dr;
        const nc = c + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
          grid[nr][nc] = 2;
          queue.push([nr, nc]);
          freshCount--;
          rotted = true;
        }
      }
    }

    if (rotted) minutes++;
  }

  return freshCount === 0 ? minutes : -1;
};

// Example usage:
const grid = [
  [2,1,1],
  [1,1,0],
  [0,1,1]
];
console.log(orangesRotting(grid)); // Output: 4

Note: The BFS ensures that all oranges rot simultaneously at each time step, mimicking the spread of rot.

6. Finding Word Ladder

A word ladder is a sequence of words where each word differs from the next by exactly one letter. This problem can be solved using BFS to find the shortest transformation path.

Property	Description	Example
startWord	Initial word to begin transformation	`"hit"`
endWord	Target word to reach	`"cog"`
wordList	List of valid words for transformation	`["hot", "dot", "dog", "lot", "log", "cog"]`

Example: Word Ladder BFS Implementation

function ladderLength(beginWord, endWord, wordList) {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return 0;

    const queue = [[beginWord, 1]];
    while (queue.length > 0) {
        const [word, depth] = queue.shift();
        if (word === endWord) return depth;

        for (let i = 0; i < word.length; i++) {
            for (let c = 97; c <= 122; c++) {
                const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
                if (wordSet.has(newWord)) {
                    queue.push([newWord, depth + 1]);
                    wordSet.delete(newWord);
                }
            }
        }
    }
    return 0;
}

// Example usage:
const beginWord = "hit";
const endWord = "cog";
const wordList = ["hot", "dot", "dog", "lot", "log", "cog"];
console.log(ladderLength(beginWord, endWord, wordList)); // Output: 5

Note: The BFS ensures the shortest path is found by exploring all transformations of the same depth before moving to the next level.

7. Solving Snakes and Ladders

The Snakes and Ladders game can be modeled as a directed graph where each cell is a node, and edges represent possible moves based on dice rolls (1-6). The goal is to find the minimum number of moves to reach the final cell (typically labeled as 100). BFS is ideal here because it explores all moves at the current depth before moving to the next, ensuring the shortest path is found.

Component	Description	Implementation
Graph Representation	Each cell (1 to 100) is a node. An edge exists from node `i` to node `j` if rolling a die can move from cell `i` to `j`.	`const graph = new Map();\nfor (let i = 1; i <= 100; i++) {\n graph.set(i, []);\n for (let j = 1; j <= 6; j++) {\n if (i + j <= 100) graph.get(i).push(i + j);\n }\n}`
Handling Snakes and Ladders	Adjust edges to reflect snakes (moving backward) or ladders (moving forward). These are typically represented as a map from start to end positions.	`const snakesAndLadders = {\n 16: 6,\n 47: 26,\n 49: 11,\n 56: 53,\n 62: 19,\n 64: 60,\n 87: 24,\n 93: 73,\n 95: 75,\n 98: 79\n};\n\n// Adjust graph edges to reflect snakes/ladders\nfor (let i = 1; i <= 100; i++) {\n const neighbors = graph.get(i);\n for (let j = 0; j < neighbors.length; j++) {\n const nextCell = neighbors[j];\n if (snakesAndLadders[nextCell]) {\n graph.get(i)[j] = snakesAndLadders[nextCell];\n }\n }\n}`
BFS Implementation	Use a queue to process nodes level by level. Track the number of moves and visited cells to avoid cycles.	`function minMovesToWin(snakesAndLadders) {\n const queue = [[1, 0]];\n const visited = new Set([1]);\n\n while (queue.length > 0) {\n const [currentCell, moves] = queue.shift();\n if (currentCell === 100) return moves;\n\n for (let nextCell = currentCell + 1; nextCell <= Math.min(currentCell + 6, 100); nextCell++) {\n if (!visited.has(nextCell)) {\n visited.add(nextCell);\n queue.push([nextCell, moves + 1]);\n }\n }\n }\n return -1;\n}`

Example: Solving Snakes and Ladders

const snakesAndLadders = {\n  16: 6,\n  47: 26,\n  49: 11,\n  56: 53,\n  62: 19,\n  64: 60,\n  87: 24,\n  93: 73,\n  95: 75,\n  98: 79\n};\n\nfunction minMovesToWin(snakesAndLadders) {\n  const queue = [[1, 0]];\n  const visited = new Set([1]);\n\n  while (queue.length > 0) {\n    const [currentCell, moves] = queue.shift();\n    if (currentCell === 100) return moves;\n\n    for (let nextCell = currentCell + 1; nextCell <= Math.min(currentCell + 6, 100); nextCell++) {\n      if (!visited.has(nextCell)) {\n        visited.add(nextCell);\n        queue.push([nextCell, moves + 1]);\n      }\n    }\n  }\n  return -1;\n}\n\nconsole.log(minMovesToWin(snakesAndLadders)); // Output: 3

8. Finding Shortest Bridge

Property	Description	Usage
BFS Algorithm	Traverses graph level-by-level to find shortest path	Used in grid-based pathfinding problems
Bridge Formation	Connects two components in a graph with minimal edges	Used to minimize cost of connecting disconnected graphs
Grid Representation	2D grid where each cell is a node	Each cell can be land (1) or water (0)

Example: Finding Shortest Bridge in Grid

function shortestBridge(grid) {
  const n = grid.length;
  const visited = Array(n).fill().map(() => Array(n).fill(false));
  const queue = [];

  // Find first island and mark all its cells
  let found = false;
  for (let i = 0; i < n; i++) {
    if (found) break;
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        dfs(i, j);
        found = true;
        break;
      }
    }
  }

  // BFS to find shortest bridge
  let steps = 0;
  while (queue.length > 0) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const [x, y] = queue.shift();
      for (const [dx, dy] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
        const nx = x + dx;
        const ny = y + dy;
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny]) {
          if (grid[nx][ny] === 1) return steps;
          visited[nx][ny] = true;
          queue.push([nx, ny]);
        }
      }
    }
    steps++;
  }

  function dfs(i, j) {
    if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] === 0 || visited[i][j]) return;
    visited[i][j] = true;
    queue.push([i, j]);
    dfs(i + 1, j);
    dfs(i - 1, j);
    dfs(i, j + 1);
    dfs(i, j - 1);
  }

  return -1;
}

Note: This algorithm uses BFS to expand from one island until it reaches the second island, ensuring minimal bridge length.

9. Validating Bipartite Graph

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no two graph vertices within the same set are adjacent. This property makes bipartite graphs useful in modeling relationships between two different types of objects.

Property	Description	Notes
Bipartite Check	Using BFS to validate if a graph is bipartite	Requires coloring each node with one of two colors, ensuring adjacent nodes have different colors

Example: Bipartite Validation Using BFS

function isBipartite(graph) {
  const color = new Array(graph.length).fill(-1);
  
  for (let i = 0; i < graph.length; i++) {
    if (color[i] === -1) {
      color[i] = 0;
      const queue = [i];
      
      while (queue.length > 0) {
        const node = queue.shift();
        const currentNodeColor = color[node];
        
        for (const neighbor of graph[node]) {
          if (color[neighbor] === -1) {
            color[neighbor] = 1 - currentNodeColor;
            queue.push(neighbor);
          } else if (color[neighbor] === currentNodeColor) {
            return false;
          }
        }
      }
    }
  }
  
  return true;
}

Note: The algorithm uses a BFS traversal to assign colors to nodes. If any two adjacent nodes end up with the same color, the graph is not bipartite.

Key Points

Bipartite graphs can be validated using BFS with a two-coloring approach
Each node is assigned one of two colors, ensuring adjacent nodes have different colors
If a conflict arises during traversal, the graph is not bipartite

10. Finding Minimum Knight Moves

Knight moves on a chessboard are unique: they can move two squares in one direction and one square perpendicular to that direction, forming an "L" shape. To find the minimum number of moves from a starting position to a target position, we can model this as a graph traversal problem and use BFS (Breadth-First Search) to guarantee the shortest path.

Property	Description	Notes
Knight Moves	Each move is one of 8 possible L-shaped moves.	Valid moves: (±2, ±1) or (±1, ±2)
BFS Strategy	Explore all positions reachable in 1 move, then 2 moves, etc.	Ensures minimum steps due to level-by-level exploration

Example: Knight Moves on 8x8 Board

function minKnightMoves(x, y) {
    // Normalize to first quadrant for symmetry
    x = Math.abs(x);
    y = Math.abs(y);
    
    // Swap if needed to ensure x >= y
    if (x < y) {
        [x, y] = [y, x];
    }

    // Special case for small moves
    if (x === 2 && y === 2) return 4;

    // BFS to find minimum moves
    const queue = [[0, 0, 0]];
    const visited = new Set();
    visited.add("0,0");

    const moves = [[2,1], [1,2], [-1,2], [-2,1], [-2,-1], [-1,-2], [1,-2], [2,-1]];

    while (queue.length > 0) {
        const [currX, currY, steps] = queue.shift();
        
        if (currX === x && currY === y) {
            return steps;
        }

        for (const [dx, dy] of moves) {
            const nextX = currX + dx;
            const nextY = currY + dy;
            const key = `${nextX},${nextY}`;
            
            if (!visited.has(key) && nextX >= -1 && nextY >= -1) {
                visited.add(key);
                queue.push([nextX, nextY, steps + 1]);
            }
        }
    }

    return -1;
}

// Example usage:
console.log(minKnightMoves(2, 1)); // Output: 1
console.log(minKnightMoves(5, 5)); // Output: 4

Note: The solution uses symmetry and normalization to reduce the search space. For small boards, special cases are handled to avoid unnecessary computation.

11. Solving Open the Lock Problem

The "Open the Lock" problem involves finding the minimum number of moves to open a lock with 4-digit combinations, where each digit can be rotated up or down. The problem is modeled as a graph traversal problem using BFS.

Property	Description
Start State	Initial combination, e.g., "0000"
Target State	Desired combination, e.g., "0009"
Neighbors	Each digit can be incremented or decremented (e.g., 0 → 1 or 9)
Forbidden States	Combinations in deadends list (e.g., ["0001", "0002"])

Example: BFS Implementation

function openLock(deadends, target) {
    const dead = new Set(deadends);
    if (dead.has("0000")) return -1;

    const queue = [["0000", 0]];
    const visited = new Set(["0000"]);

    while (queue.length > 0) {
        const [current, steps] = queue.shift();

        if (current === target) return steps;

        for (let i = 0; i < 4; i++) {
            const up = current.slice(0, i) + ((+current[i] + 1) % 10) + current.slice(i + 1);
            const down = current.slice(0, i) + ((+current[i] + 9) % 10) + current.slice(i + 1);

            if (!visited.has(up) && !dead.has(up)) {
                visited.add(up);
                queue.push([up, steps + 1]);
            }
            if (!visited.has(down) && !dead.has(down)) {
                visited.add(down);
                queue.push([down, steps + 1]);
            }
        }
    }

    return -1;
}

// Example usage:
const deadends = ["0001", "0002"];
const target = "0009";
console.log(openLock(deadends, target)); // Output: 4

Note: The BFS ensures the shortest path is found by exploring all combinations at each step before moving to the next level.

12. Finding Bus Routes

Property	Description	Example
busRoutes	List of bus routes, where each route is an array of stops	`[[0,1,2,3], [2,3,4,5]]`
sourceStop	Starting bus stop	`0`
targetStop	Destination bus stop	`5`

Example: Finding Bus Routes

function findBusRoutes(busRoutes, sourceStop, targetStop) {
    const graph = new Map();
    const queue = [[sourceStop, 0]];
    const visited = new Set();

    // Build graph from bus routes
    for (const route of busRoutes) {
        for (let i = 0; i < route.length; i++) {
            const stop = route[i];
            if (!graph.has(stop)) graph.set(stop, []);
            graph.get(stop).push(...route);
        }
    }

    // BFS to find shortest route
    while (queue.length > 0) {
        const [currentStop, distance] = queue.shift();
        if (currentStop === targetStop) return distance;

        if (visited.has(currentStop)) continue;
        visited.add(currentStop);

        const nextStops = graph.get(currentStop) || [];
        for (const stop of nextStops) {
            if (!visited.has(stop)) {
                queue.push([stop, distance + 1]);
            }
        }
    }

    return -1; // No route found
}

// Example usage:
const routes = [[0,1,2,3], [2,3,4,5]];
const result = findBusRoutes(routes, 0, 5);
console.log(result); // Output: 2 (via stop 2 and 3)

Note: BFS ensures the minimum number of bus changes to reach the destination.