Graph Traversals — The Complete Guide

function bfs(graph: Map<number, number[]>, start: number): void {
  const visited = new Set<number>();
  const queue: number[] = [start];
  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift()!; // dequeue front
    // Process node here

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);   // mark BEFORE enqueuing
        queue.push(neighbor);
      }
    }
  }
}
// Time: O(V + E) — visit every vertex and edge once
// Space: O(V) — visited set + queue
// Key: mark visited WHEN ENQUEUING, not when dequeuing.
// This prevents the same node from being added to the queue multiple times.

function dfs(
  graph: Map<number, number[]>,
  node: number,
  visited: Set<number>
): void {
  visited.add(node);
  // Process node here

  for (const neighbor of graph.get(node) ?? []) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited);
    }
  }
}

// Iterative version (explicit stack):
function dfsIterative(graph: Map<number, number[]>, start: number): void {
  const visited = new Set<number>();
  const stack: number[] = [start];

  while (stack.length > 0) {
    const node = stack.pop()!;
    if (visited.has(node)) continue;
    visited.add(node);
    // Process node here

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
      }
    }
  }
}
// Time: O(V + E). Space: O(V) for visited + O(V) stack depth.

function bfsGrid(grid: string[][], startR: number, startC: number): void {
  const rows = grid.length;
  const cols = grid[0].length;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]; // 4 directions

  const queue: [number, number][] = [[startR, startC]];
  grid[startR][startC] = '0'; // mark visited (or use a separate set)

  while (queue.length > 0) {
    const [r, c] = queue.shift()!;

    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;

      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
        grid[nr][nc] = '0'; // mark visited BEFORE enqueuing
        queue.push([nr, nc]);
      }
    }
  }
}
// Grid DFS is the same but uses recursion or a stack instead of a queue.
// The directions array [1,0], [-1,0], [0,1], [0,-1] handles 4-directional movement.
// For 8-directional, add the 4 diagonals.
// When to use: Number of Islands, Flood Fill, Shortest Path in Binary Matrix,
// Rotting Oranges, Surrounded Regions

function bfsShortestPath(graph: Map<number, number[]>, start: number, target: number): number {
  const visited = new Set<number>();
  const queue: number[] = [start];
  visited.add(start);
  let distance = 0;

  while (queue.length > 0) {
    const levelSize = queue.length; // nodes at current distance

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

      if (node === target) return distance; // found!

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

    distance++; // all nodes at current distance processed
  }

  return -1; // target not reachable
}
// Key: the inner loop processes exactly one "level" (all nodes at the same distance).
// After the inner loop, increment distance.
// This guarantees the first time we reach the target, it's at the shortest distance.
// When to use: Word Ladder, Shortest Path in Binary Matrix, Rotting Oranges,
// minimum steps to reach a state

function orangesRotting(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length;
  const queue: [number, number][] = [];
  let fresh = 0;

  // Enqueue ALL rotten oranges as starting points
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c]);
      if (grid[r][c] === 1) fresh++;
    }
  }

  if (fresh === 0) return 0; // no fresh oranges

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

  while (queue.length > 0 && fresh > 0) {
    const levelSize = queue.length;
    for (let i = 0; i < levelSize; i++) {
      const [r, c] = queue.shift()!;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
          grid[nr][nc] = 2; // rot it
          fresh--;
          queue.push([nr, nc]);
        }
      }
    }
    minutes++;
  }

  return fresh === 0 ? minutes : -1;
}
// Multi-source BFS: all rotten oranges spread simultaneously.
// Each BFS level = 1 minute. When fresh === 0, we're done.
// Time: O(m × n). Space: O(m × n) for the queue.

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  // Build adjacency list and in-degree array
  const graph = new Map<number, number[]>();
  const inDegree = new Array(numCourses).fill(0);

  for (const [course, prereq] of prerequisites) {
    if (!graph.has(prereq)) graph.set(prereq, []);
    graph.get(prereq)!.push(course);
    inDegree[course]++;
  }

  // Start with all courses that have no prerequisites
  const queue: number[] = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const order: number[] = [];

  while (queue.length > 0) {
    const course = queue.shift()!;
    order.push(course);

    for (const next of graph.get(course) ?? []) {
      inDegree[next]--;
      if (inDegree[next] === 0) {
        queue.push(next); // all prerequisites satisfied
      }
    }
  }

  // If we processed all courses, the order is valid
  return order.length === numCourses ? order : [];
}
// Time: O(V + E). Space: O(V + E).
// If order.length < numCourses, there's a cycle → impossible.
// Kahn's naturally detects cycles: nodes in a cycle never reach in-degree 0.

function hasCycle(numNodes: number, edges: number[][]): boolean {
  const graph = new Map<number, number[]>();
  for (const [u, v] of edges) {
    if (!graph.has(u)) graph.set(u, []);
    graph.get(u)!.push(v);
  }

  // 0 = white (unvisited), 1 = gray (in path), 2 = black (done)
  const color = new Array(numNodes).fill(0);

  function dfs(node: number): boolean {
    color[node] = 1; // gray — currently exploring

    for (const neighbor of graph.get(node) ?? []) {
      if (color[neighbor] === 1) return true;  // back edge → cycle!
      if (color[neighbor] === 0 && dfs(neighbor)) return true;
    }

    color[node] = 2; // black — fully processed
    return false;
  }

  for (let i = 0; i < numNodes; i++) {
    if (color[i] === 0 && dfs(i)) return true;
  }

  return false;
}
// Gray → gray = back edge = cycle in directed graph.
// Black nodes are safe — they've been fully explored with no cycle.
// This is the standard technique for Course Schedule (can you finish all courses?).

Graph (undirected):
    0 — 1 — 3
    |   |
    2   4

Adjacency list:
  0: [1, 2]
  1: [0, 3, 4]
  2: [0]
  3: [1]
  4: [1]

BFS from node 0 (queue):
  Queue: [0]         Visit: 0    → Process 0, enqueue neighbors 1, 2
  Queue: [1, 2]      Visit: 1    → Process 1, enqueue neighbors 3, 4
  Queue: [2, 3, 4]   Visit: 2    → Process 2, no new neighbors
  Queue: [3, 4]      Visit: 3    → Process 3, no new neighbors
  Queue: [4]          Visit: 4    → Process 4, no new neighbors
  
  BFS order: 0, 1, 2, 3, 4  (level by level)
  Level 0: {0}
  Level 1: {1, 2}
  Level 2: {3, 4}

DFS from node 0 (recursive):
  Visit 0 → recurse to neighbor 1
    Visit 1 → recurse to neighbor 3
      Visit 3 → no unvisited neighbors, backtrack
    Back to 1 → recurse to neighbor 4
      Visit 4 → no unvisited neighbors, backtrack
    Back to 1 → backtrack
  Back to 0 → recurse to neighbor 2
    Visit 2 → no unvisited neighbors, backtrack
  
  DFS order: 0, 1, 3, 4, 2  (depth first)

Key difference:
  BFS: 0 → {1,2} → {3,4}     (explores by distance)
  DFS: 0 → 1 → 3 → 4 → 2     (explores one branch fully before the next)

Grid:
  1 1 0 0 0
  1 1 0 0 0
  0 0 1 0 0
  0 0 0 1 1

Scan left-to-right, top-to-bottom:

(0,0) = '1' → NEW ISLAND #1
  DFS flood fill: (0,0)→(1,0)→(1,1)→(0,1) all become '0'
  Grid after:
    0 0 0 0 0
    0 0 0 0 0
    0 0 1 0 0
    0 0 0 1 1

(0,1) to (1,1) = '0' → skip

(2,2) = '1' → NEW ISLAND #2
  DFS flood fill: (2,2) becomes '0'
  Grid after:
    0 0 0 0 0
    0 0 0 0 0
    0 0 0 0 0
    0 0 0 1 1

(3,3) = '1' → NEW ISLAND #3
  DFS flood fill: (3,3)→(3,4) both become '0'
  Grid after:
    0 0 0 0 0
    0 0 0 0 0
    0 0 0 0 0
    0 0 0 0 0

Answer: 3 islands

Key: Each DFS call from the outer loop discovers one complete island.
Sinking land to '0' prevents double-counting.

Courses: 0, 1, 2, 3
Prerequisites: [[1,0], [2,0], [3,1], [3,2]]
  Meaning: 0→1, 0→2, 1→3, 2→3

In-degrees: [0, 1, 1, 2]
  Course 0: 0 prerequisites
  Course 1: 1 prerequisite (course 0)
  Course 2: 1 prerequisite (course 0)
  Course 3: 2 prerequisites (courses 1 and 2)

Step 1: Queue = [0] (in-degree 0)
  Process 0 → order = [0]
  Decrement neighbors: inDegree[1]=0, inDegree[2]=0
  Queue = [1, 2]

Step 2: Process 1 → order = [0, 1]
  Decrement neighbors: inDegree[3]=1
  Queue = [2]

Step 3: Process 2 → order = [0, 1, 2]
  Decrement neighbors: inDegree[3]=0
  Queue = [3]

Step 4: Process 3 → order = [0, 1, 2, 3]
  Queue = []

Answer: [0, 1, 2, 3] ✓ (valid topological order)
All 4 courses processed → no cycle.

If a cycle existed, some nodes would never reach in-degree 0,
and order.length < numCourses → return [].

Can you model the problem as nodes and edges?
├── NO  → Not a graph problem. Consider arrays, trees, or other patterns.
└── YES → Do you need the SHORTEST PATH (unweighted)?
          ├── YES → BFS with level tracking (Template 4)
          │         Word Ladder, Shortest Path in Binary Matrix, Rotting Oranges
          └── NO  → Do you need TOPOLOGICAL ORDER (dependencies)?
                    ├── YES → Kahn's BFS (in-degree) or DFS post-order
                    │         Course Schedule, Alien Dictionary
                    └── NO  → Do you need to DETECT CYCLES?
                              ├── YES → Undirected: DFS + parent check
                              │         Directed: 3-color DFS (gray→gray)
                              └── NO  → Do you need CONNECTED COMPONENTS?
                                        ├── YES → DFS/BFS from each unvisited node
                                        │         Number of Islands, Number of Provinces
                                        └── NO  → Is it a GRID problem?
                                                  ├── YES → Grid DFS/BFS (Template 3)
                                                  │         Flood Fill, Surrounded Regions
                                                  └── NO  → General BFS or DFS
                                                            Clone Graph, Is Bipartite