Breadth-First Search

What is BFS?

Breadth-First Search (BFS) is a graph/tree traversal algorithm that explores all neighbors at the current depth before moving to nodes at the next depth level. It uses a queue (FIFO) to track which nodes to visit next.

Key Idea: Visit ALL nodes at distance 1, then distance 2, then distance 3...

How It Works

Algorithm:
  1. Start at the root/source node, mark it as visited
  2. Add it to the queue
  3. While the queue is not empty:
     a. Dequeue the front node (current)
     b. Process current
     c. For each unvisited neighbor:
        - Mark as visited
        - Add to queue
  4. Repeat until queue is empty

Data structure: Queue (FIFO — first in, first out)

Visualization

Graph:
        A
       / \
      B   C
     / \   \
    D   E   F

BFS from A (level by level):

  Queue: [A]          → Visit A     → Level 0: A
  Queue: [B, C]       → Visit B     → Level 1: B, C
  Queue: [C, D, E]    → Visit C
  Queue: [D, E, F]    → Visit D     → Level 2: D, E, F
  Queue: [E, F]       → Visit E
  Queue: [F]          → Visit F
  Queue: []           → Done

Traversal order: A → B → C → D → E → F

Compare to DFS (goes deep first):
  DFS order:          A → B → D → E → C → F
  BFS order:          A → B → C → D → E → F  ✓ level by level

Time & Space Complexity

Time Complexity:   O(V + E)
  - V = number of vertices (nodes)
  - E = number of edges
  - Each node and edge is visited at most once

Space Complexity:  O(V)
  - Queue holds at most the entire "frontier" (widest level)
  - In a balanced binary tree: O(V/2) ≈ O(V) at the last level

BFS properties:
  ✓ Guarantees shortest path in UNWEIGHTED graphs
  ✓ Complete — always finds a solution if one exists
  ✓ Optimal for fewest hops / minimum steps
  ✗ Uses more memory than DFS (stores entire frontier)
  ✗ Not suitable for weighted shortest path (use Dijkstra)

When to Use BFS

Use BFS when:
  ✓ Finding the shortest path in an unweighted graph
  ✓ Finding all nodes within a certain distance
  ✓ Level-order traversal of a tree
  ✓ Checking if a graph is bipartite
  ✓ Finding connected components
  ✓ Web crawling (exploring links layer by layer)
  ✓ Social network "degrees of separation"
  ✓ GPS — fewest turns/roads (unweighted)

Use DFS instead when:
  ✗ Detecting cycles
  ✗ Topological sorting
  ✗ Solving mazes (path existence, not shortest)
  ✗ Memory is constrained (DFS uses O(depth) vs BFS O(width))

Use Dijkstra instead when:
  ✗ Graph has weighted edges and you need shortest path by weight

TypeScript Implementation

// BFS on a graph (adjacency list)
function bfs(graph: Map<string, string[]>, start: string): string[] {
  const visited = new Set<string>();   // Track visited nodes
  const queue: string[] = [start];    // FIFO queue
  const order: string[] = [];         // Traversal result

  visited.add(start);

  while (queue.length > 0) {
    const current = queue.shift()!;   // Dequeue front node
    order.push(current);

    for (const neighbor of graph.get(current) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);        // Mark before enqueuing (prevents duplicates)
        queue.push(neighbor);
      }
    }
  }

  return order;
}

// BFS shortest path — returns fewest hops from start to end
function bfsShortestPath(
  graph: Map<string, string[]>,
  start: string,
  end: string
): string[] | null {
  if (start === end) return [start];

  const visited = new Set<string>();
  const queue: Array<{ node: string; path: string[] }> = [
    { node: start, path: [start] },
  ];
  visited.add(start);

  while (queue.length > 0) {
    const { node: current, path } = queue.shift()!;

    for (const neighbor of graph.get(current) ?? []) {
      if (!visited.has(neighbor)) {
        const newPath = [...path, neighbor];

        if (neighbor === end) return newPath; // Found shortest path

        visited.add(neighbor);
        queue.push({ node: neighbor, path: newPath });
      }
    }
  }

  return null; // No path found
}

// BFS level-order tree traversal
interface TreeNode {
  val: number;
  left?: TreeNode;
  right?: TreeNode;
}

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];

  const result: number[][] = [];
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;   // Snapshot current level width
    const level: number[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      level.push(node.val);

      if (node.left) queue.push(node.left);   // Enqueue children
      if (node.right) queue.push(node.right);
    }

    result.push(level); // Each inner array is one level
  }

  return result;
}

// Usage
const graph = new Map<string, string[]>([
  ['A', ['B', 'C']],
  ['B', ['A', 'D', 'E']],
  ['C', ['A', 'F']],
  ['D', ['B']],
  ['E', ['B']],
  ['F', ['C']],
]);

console.log(bfs(graph, 'A'));
// → ['A', 'B', 'C', 'D', 'E', 'F']

console.log(bfsShortestPath(graph, 'D', 'F'));
// → ['D', 'B', 'A', 'C', 'F']

Python Implementation

from collections import deque  # Efficient O(1) popleft

def bfs(graph: dict[str, list[str]], start: str) -> list[str]:
    """Traverse graph using BFS, return visit order."""
    visited = {start}           # Set for O(1) lookup
    queue = deque([start])      # deque is faster than list for queue ops
    order = []

    while queue:
        current = queue.popleft()   # O(1) dequeue from front
        order.append(current)

        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)   # Mark before enqueuing
                queue.append(neighbor)

    return order


def bfs_shortest_path(
    graph: dict[str, list[str]], start: str, end: str
) -> list[str] | None:
    """Return shortest path (fewest hops) from start to end."""
    if start == end:
        return [start]

    visited = {start}
    queue = deque([[start]])        # Queue of paths, not just nodes

    while queue:
        path = queue.popleft()
        current = path[-1]          # Last node in current path

        for neighbor in graph[current]:
            if neighbor not in visited:
                new_path = path + [neighbor]

                if neighbor == end:
                    return new_path  # First time we reach end = shortest

                visited.add(neighbor)
                queue.append(new_path)

    return None  # No path found


def bfs_levels(graph: dict[str, list[str]], start: str) -> list[list[str]]:
    """Return nodes grouped by their distance from start."""
    visited = {start}
    queue = deque([(start, 0)])     # (node, depth)
    levels: list[list[str]] = []

    while queue:
        node, depth = queue.popleft()

        # Extend levels list if needed
        if depth == len(levels):
            levels.append([])

        levels[depth].append(node)

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

    return levels


def bfs_connected_components(graph: dict[str, list[str]]) -> list[list[str]]:
    """Find all connected components in an undirected graph."""
    visited = set()
    components = []

    for node in graph:
        if node not in visited:
            # BFS from each unvisited node discovers a new component
            component = []
            queue = deque([node])
            visited.add(node)

            while queue:
                current = queue.popleft()
                component.append(current)

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

            components.append(component)

    return components


# Usage
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C'],
}

print(bfs(graph, 'A'))
# → ['A', 'B', 'C', 'D', 'E', 'F']

print(bfs_shortest_path(graph, 'D', 'F'))
# → ['D', 'B', 'A', 'C', 'F']

print(bfs_levels(graph, 'A'))
# → [['A'], ['B', 'C'], ['D', 'E', 'F']]

BFS vs DFS

Rule of thumb:
  → "Shortest / fewest steps"  →  BFS
  → "Does a path exist?"       →  DFS
  → "Weighted shortest path"   →  Dijkstra