04 — Graph BFS & DFS

Representations

// Adjacency List (preferred — sparse graphs)
const adj: number[][] = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
  adj[u].push(v);
  adj[v].push(u); // Undirected
}

// Adjacency Matrix (dense graphs)
const matrix: boolean[][] = Array.from({ length: n }, () => new Array(n).fill(false));

---

BFS (Breadth-First Search)

Level-by-level traversal. Shortest path in unweighted graphs.

function bfs(adj: number[][], start: number, n: number): number[] {
  const dist = new Array(n).fill(-1);
  dist[start] = 0;
  const queue = [start];
  
  while (queue.length > 0) {
    const u = queue.shift()!;
    for (const v of adj[u]) {
      if (dist[v] === -1) {
        dist[v] = dist[u] + 1;
        queue.push(v);
      }
    }
  }
  return dist;
}

DFS (Depth-First Search)

Go as deep as possible, then backtrack.

function dfs(adj: number[][], start: number, n: number): boolean[] {
  const visited = new Array(n).fill(false);
  
  function explore(u: number) {
    visited[u] = true;
    for (const v of adj[u]) {
      if (!visited[v]) explore(v);
    }
  }
  
  explore(start);
  return visited;
}

---

Connected Components

function countComponents(n: number, adj: number[][]): number {
  const visited = new Array(n).fill(false);
  let count = 0;
  
  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      count++;
      // BFS or DFS from i
      const queue = [i];
      visited[i] = true;
      while (queue.length) {
        const u = queue.shift()!;
        for (const v of adj[u]) {
          if (!visited[v]) {
            visited[v] = true;
            queue.push(v);
          }
        }
      }
    }
  }
  return count;
}

---

Cycle Detection

Undirected Graph (DFS)

function hasCycleUndirected(adj: number[][], n: number): boolean {
  const visited = new Array(n).fill(false);
  
  function dfs(u: number, parent: number): boolean {
    visited[u] = true;
    for (const v of adj[u]) {
      if (!visited[v]) {
        if (dfs(v, u)) return true;
      } else if (v !== parent) {
        return true; // Back edge → cycle
      }
    }
    return false;
  }
  
  for (let i = 0; i < n; i++) {
    if (!visited[i] && dfs(i, -1)) return true;
  }
  return false;
}

Directed Graph (DFS — 3 colors)

function hasCycleDirected(adj: number[][], n: number): boolean {
  const color = new Array(n).fill(0); // 0=white, 1=gray, 2=black
  
  function dfs(u: number): boolean {
    color[u] = 1; // Gray (in progress)
    for (const v of adj[u]) {
      if (color[v] === 1) return true;  // Back edge → cycle
      if (color[v] === 0 && dfs(v)) return true;
    }
    color[u] = 2; // Black (done)
    return false;
  }
  
  for (let i = 0; i < n; i++) {
    if (color[i] === 0 && dfs(i)) return true;
  }
  return false;
}

---

Topological Sort

Linear ordering of DAG vertices. Every edge u → v means u comes before v.

// Kahn's Algorithm (BFS-based)
function topSort(adj: number[][], n: number): number[] {
  const inDegree = new Array(n).fill(0);
  for (let u = 0; u < n; u++) {
    for (const v of adj[u]) inDegree[v]++;
  }
  
  const queue = [];
  for (let i = 0; i < n; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }
  
  const order: number[] = [];
  while (queue.length) {
    const u = queue.shift()!;
    order.push(u);
    for (const v of adj[u]) {
      inDegree[v]--;
      if (inDegree[v] === 0) queue.push(v);
    }
  }
  
  return order.length === n ? order : []; // Empty if cycle exists
}

---

Bipartite Check (2-Coloring)

function isBipartite(adj: number[][], n: number): boolean {
  const color = new Array(n).fill(-1);
  
  for (let i = 0; i < n; i++) {
    if (color[i] !== -1) continue;
    color[i] = 0;
    const queue = [i];
    
    while (queue.length) {
      const u = queue.shift()!;
      for (const v of adj[u]) {
        if (color[v] === -1) {
          color[v] = 1 - color[u];
          queue.push(v);
        } else if (color[v] === color[u]) {
          return false; // Same color → not bipartite
        }
      }
    }
  }
  return true;
}

---

Grid BFS (Shortest Path in Matrix)

function shortestPath(grid: number[][], start: [number, number], end: [number, number]): number {
  const [rows, cols] = [grid.length, grid[0].length];
  const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
  const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
  
  const queue: [number, number, number][] = [[start[0], start[1], 0]];
  visited[start[0]][start[1]] = true;
  
  while (queue.length) {
    const [r, c, dist] = queue.shift()!;
    if (r === end[0] && c === end[1]) return dist;
    
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc] && grid[nr][nc] === 0) {
        visited[nr][nc] = true;
        queue.push([nr, nc, dist + 1]);
      }
    }
  }
  return -1;
}

---

Key Takeaways

• BFS = shortest path (unweighted), level-order; DFS = cycle detection, topological sort
• Cycle detection: undirected = parent check; directed = 3-color (white/gray/black)
• Topological sort (Kahn's) = BFS with in-degree; also detects cycles in DAGs
• Bipartite = 2-colorable = no odd-length cycles
• Grid problems are just graph problems — use BFS with 4-directional neighbors