Breadth-First Search

from collections import deque

def bfs(graph, start):
    """Basic BFS traversal. Returns nodes in visit order.
    graph = adjacency list {node: [neighbors]}.
    Uses deque for O(1) popleft — never use list.pop(0)."""
    visited = {start}           # Mark visited on ENQUEUE
    queue = deque([start])      # FIFO queue
    order = []

    while queue:
        node = queue.popleft()  # Process front of queue
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)  # Mark BEFORE enqueueing
                queue.append(neighbor)

    return order
      

from collections import deque

def bfs_levels(graph, start):
    """Returns nodes grouped by level (distance from start).
    Level 0 = [start], Level 1 = start's neighbors, etc.
    The key trick: snapshot len(queue) at each level's start."""
    visited = {start}
    queue = deque([start])
    levels = []

    while queue:
        level_size = len(queue)  # How many nodes at this level
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node)

            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

        levels.append(current_level)

    return levels
# Result: [[A], [B, C], [D, E, F], ...]
# levels[i] contains all nodes at distance i from start
      

from collections import deque

def shortest_path(graph, start, end):
    """Find the shortest path (fewest edges) from start to end.
    Returns the path as a list, or None if no path exists.
    
    Instead of storing full paths (expensive), track predecessors
    and reconstruct the path at the end."""
    if start == end:
        return [start]

    visited = {start}
    queue = deque([start])
    predecessor = {start: None}  # Track how we reached each node

    while queue:
        node = queue.popleft()

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                predecessor[neighbor] = node
                queue.append(neighbor)

                if neighbor == end:
                    # Reconstruct path by following predecessors back
                    path = []
                    current = end
                    while current is not None:
                        path.append(current)
                        current = predecessor[current]
                    return path[::-1]  # Reverse: start → end

    return None  # No path exists
      

function shortestPath(graph, start, end) {
  if (start === end) return [start];

  const visited = new Set([start]);
  const queue = [start];
  const predecessor = new Map([[start, null]]);

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

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

        if (neighbor === end) {
          // Reconstruct path
          const path = [];
          let current = end;
          while (current !== null) {
            path.push(current);
            current = predecessor.get(current);
          }
          return path.reverse();
        }
      }
    }
  }
  return null;
}
      

from collections import deque

def grid_bfs(grid, start_row, start_col):
    """BFS on a 2D grid. Returns set of all reachable cells.
    Useful for flood fill, connected components, shortest path.
    
    Treats each cell as a node. Neighbors are the 4 adjacent cells
    (up, down, left, right). '#' cells are walls (impassable)."""
    rows, cols = len(grid), len(grid[0])
    visited = set()
    visited.add((start_row, start_col))
    queue = deque([(start_row, start_col, 0)])  # (row, col, distance)

    # 4-directional movement: right, left, down, up
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while queue:
        r, c, dist = queue.popleft()

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            # Check bounds, not visited, and not a wall
            if (0 <= nr < rows and 0 <= nc < cols
                    and (nr, nc) not in visited
                    and grid[nr][nc] != '#'):
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))

    return visited
      

from collections import deque

def oranges_rotting(grid):
    """How many minutes until all oranges rot?
    Rotten oranges (2) spread to adjacent fresh oranges (1) each minute.
    
    Multi-source BFS: start from ALL rotten oranges simultaneously.
    Each BFS level = one minute of spreading."""
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh_count = 0

    # Enqueue ALL rotten oranges as starting points
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))  # (row, col, time)
            elif grid[r][c] == 1:
                fresh_count += 1

    if fresh_count == 0:
        return 0  # Nothing to rot

    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    max_time = 0

    while queue:
        r, c, time = queue.popleft()

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and grid[nr][nc] == 1):
                grid[nr][nc] = 2  # Mark as rotten (acts as visited)
                fresh_count -= 1
                max_time = time + 1
                queue.append((nr, nc, time + 1))

    return max_time if fresh_count == 0 else -1
      

function gridBFS(grid, startRow, startCol) {
  /**
   * BFS on a 2D grid. Returns distance to every reachable cell.
   * grid[r][c] === '#' means a wall. Otherwise passable.
   * Uses a queue of [row, col, distance] tuples.
   */
  const rows = grid.length, cols = grid[0].length;
  const dist = Array.from({ length: rows }, () => Array(cols).fill(-1));
  dist[startRow][startCol] = 0;

  const queue = [[startRow, startCol, 0]];
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]]; // right, left, down, up
  let head = 0; // Use index instead of shift() to avoid O(n) shifts

  while (head < queue.length) {
    const [r, c, d] = queue[head++];

    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
          && dist[nr][nc] === -1 && grid[nr][nc] !== '#') {
        dist[nr][nc] = d + 1;
        queue.push([nr, nc, d + 1]);
      }
    }
  }
  return dist; // dist[r][c] = shortest distance, or -1 if unreachable
}

// Example: find distances in a 5x5 maze
const maze = [
  ['.','.','.','#','.'],
  ['.','.','#','.','.'],
  ['.','.','.','.','.'],
  ['#','#','.','.','#'],
  ['.','.','.','.','.'],
];
const distances = gridBFS(maze, 0, 0);
console.log(distances[4][4]); // shortest path from (0,0) to (4,4)
      

from collections import deque

def bidirectional_bfs(graph, start, end):
    """Find shortest path using BFS from BOTH ends simultaneously.
    
    Regular BFS explores O(b^d) nodes where b=branching factor, d=distance.
    Bidirectional explores O(2 * b^(d/2)) — exponentially fewer.
    
    Particularly effective for word ladder and social network distance
    where the graph is wide but the path is relatively short.
    """
    if start == end:
        return [start]

    # Forward BFS from start, backward BFS from end
    front_visited = {start: None}   # node → predecessor
    back_visited = {end: None}      # node → predecessor
    front_queue = deque([start])
    back_queue = deque([end])

    while front_queue and back_queue:
        # Expand the SMALLER frontier (optimization)
        if len(front_queue) <= len(back_queue):
            meeting = _expand(graph, front_queue, front_visited, back_visited)
        else:
            meeting = _expand(graph, back_queue, back_visited, front_visited)

        if meeting is not None:
            return _build_path(meeting, front_visited, back_visited)

    return None  # No path exists

def _expand(graph, queue, visited, other_visited):
    """Expand one level of BFS. Returns meeting node if frontiers meet."""
    level_size = len(queue)
    for _ in range(level_size):
        node = queue.popleft()
        for neighbor in graph.get(node, []):
            if neighbor in other_visited:
                # Frontiers met! Record predecessor and return
                visited[neighbor] = node
                return neighbor
            if neighbor not in visited:
                visited[neighbor] = node
                queue.append(neighbor)
    return None

def _build_path(meeting, front_visited, back_visited):
    """Reconstruct path from start → meeting ← end."""
    # Forward path: start → meeting
    path = []
    node = meeting
    while node is not None:
        path.append(node)
        node = front_visited.get(node)
    path.reverse()

    # Backward path: meeting → end
    node = back_visited.get(meeting)
    while node is not None:
        path.append(node)
        node = back_visited.get(node)

    return path
      

from collections import deque

def zero_one_bfs(graph, start, n):
    """Shortest path when edges have weight 0 or 1.
    graph[u] = list of (v, weight) where weight is 0 or 1.
    
    Use a deque instead of a priority queue:
    - Weight 0 edges: add to FRONT (like they're free)
    - Weight 1 edges: add to BACK (like regular BFS)
    
    This gives O(V + E) instead of Dijkstra's O(E log V)."""
    dist = [float('inf')] * n
    dist[start] = 0
    dq = deque([start])

    while dq:
        u = dq.popleft()

        for v, w in graph[u]:
            new_dist = dist[u] + w
            if new_dist < dist[v]:
                dist[v] = new_dist
                if w == 0:
                    dq.appendleft(v)  # Free edge → front of deque
                else:
                    dq.append(v)      # Cost-1 edge → back of deque

    return dist
      

from collections import deque

def word_ladder(begin_word, end_word, word_list):
    """Find shortest transformation: begin_word → end_word,
    changing one letter at a time, each step must be in word_list.
    
    This is BFS on an implicit graph:
    - Nodes: words in the dictionary
    - Edges: words differing by exactly one letter
    - We want the shortest path (fewest transformations)
    
    Example: "hit" → "hot" → "dot" → "dog" → "cog" (4 steps)"""
    word_set = set(word_list)
    if end_word not in word_set:
        return 0  # Target not in dictionary

    queue = deque([(begin_word, 1)])  # (current_word, steps)
    visited = {begin_word}

    while queue:
        word, steps = queue.popleft()

        # Try changing each letter to every letter a-z
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                if c == word[i]:
                    continue  # Skip same letter

                # Build the new word with one letter changed
                new_word = word[:i] + c + word[i+1:]

                if new_word == end_word:
                    return steps + 1  # Found it!

                if new_word in word_set and new_word not in visited:
                    visited.add(new_word)
                    queue.append((new_word, steps + 1))

    return 0  # No transformation sequence exists

# Example
words = ["hot", "dot", "dog", "lot", "log", "cog"]
result = word_ladder("hit", "cog", words)
print(f"Shortest transformation: {result} steps")
# hit → hot → dot → dog → cog = 5 steps (including start word)