• Overview and Representations
• Breadth-First Search (BFS)
• Depth-First Search (DFS)
• Bidirectional Search
• Common Applications
• Pitfalls and Tips
• Exercises

• Graphs: directed/undirected, weighted/unweighted, adjacency list vs. matrix.
• Traversal: systematically visit nodes/edges to explore connectivity and structure.
• Visited set: avoid cycles and repeated work; track parent to reconstruct paths.

// BFS: shortest paths in unweighted graphs
function bfs(adj, s) { // adj: Array<Array<number>>, s: source index
  const n = adj.length;
  const dist = Array(n).fill(Infinity);
  const parent = Array(n).fill(-1);
  const q = [];
  dist[s] = 0; q.push(s);
  for (let qi = 0; qi < q.length; qi++) {
    const u = q[qi];
    for (const v of adj[u]) if (dist[v] === Infinity) {
      dist[v] = dist[u] + 1; parent[v] = u; q.push(v);
    }
  }
  return { dist, parent };
}

function reconstructPath(parent, t) {
  const path = [];
  for (let v = t; v !== -1; v = parent[v]) path.push(v);
  return path.reverse();
}

• Complexity: O(n + m) with adjacency list.
• Properties: first time you reach a node is via a shortest path (unweighted).

// DFS: pre/post times, components, cycle detection
function dfs(adj) {
  const n = adj.length;
  const vis = Array(n).fill(false);
  const pre = Array(n).fill(0), post = Array(n).fill(0);
  let t = 0; const order = [];
  function go(u) {
    vis[u] = true; pre[u] = ++t;
    for (const v of adj[u]) if (!vis[v]) go(v);
    post[u] = ++t; order.push(u);
  }
  for (let u = 0; u < n; u++) if (!vis[u]) go(u);
  return { pre, post, order };
}

// Cycle detection in directed graph during DFS
function hasCycleDirected(adj) {
  const n = adj.length, state = Array(n).fill(0); // 0=unseen,1=stack,2=done
  function go(u) {
    state[u] = 1;
    for (const v of adj[u]) {
      if (state[v] === 1) return true;
      if (state[v] === 0 && go(v)) return true;
    }
    state[u] = 2; return false;
  }
  for (let u = 0; u < n; u++) if (state[u] === 0 && go(u)) return true;
  return false;
}

• Applications: topological sort, SCC, bridges/articulation points.
• Iterative DFS: use an explicit stack to avoid recursion limits.

// Bidirectional search for shortest path in unweighted graphs
function bidirectionalBFS(adj, s, t) {
  if (s === t) return [s];
  const n = adj.length;
  const distS = Array(n).fill(Infinity), distT = Array(n).fill(Infinity);
  const parS = Array(n).fill(-1), parT = Array(n).fill(-1);
  let qS = [s], qT = [t];
  distS[s] = 0; distT[t] = 0;
  let meet = -1;
  while (qS.length && qT.length) {
    // expand smaller frontier
    if (qS.length <= qT.length) {
      const next = [];
      for (const u of qS) {
        for (const v of adj[u]) if (distS[v] === Infinity) {
          distS[v] = distS[u] + 1; parS[v] = u; next.push(v);
          if (distT[v] !== Infinity) { meet = v; break; }
        }
        if (meet !== -1) break;
      }
      if (meet !== -1) break; qS = next;
    } else {
      const next = [];
      for (const u of qT) {
        for (const v of adj[u]) if (distT[v] === Infinity) {
          distT[v] = distT[u] + 1; parT[v] = u; next.push(v);
          if (distS[v] !== Infinity) { meet = v; break; }
        }
        if (meet !== -1) break;
      }
      if (meet !== -1) break; qT = next;
    }
  }
  if (meet === -1) return [];
  // reconstruct s..meet and meet..t
  const left = []; for (let v = meet; v !== -1; v = parS[v]) left.push(v);
  const right = []; for (let v = meet; v !== -1; v = parT[v]) right.push(v);
  right.pop(); right.reverse();
  return left.reverse().concat(right);
}

• Benefit: reduces explored nodes from O(b^d) to roughly O(2·b^{d/2}).
• When to use: known target, unweighted graph, efficient frontier checks.

• Connectivity: components, reachability, shortest paths (unweighted).
• Ordering: DFS finishing order → topological sort on DAGs.
• Structure: bridges, articulation points, bipartite check (BFS coloring).

• Visited timing: mark when pushing/enqueuing to avoid duplicates.
• Edge cases: self-loops, parallel edges; directed vs. undirected behavior.
• Memory: queues can grow large; consider layered processing.

1. Implement BFS to compute shortest paths and reconstruct the path to a target.
2. Write iterative DFS using an explicit stack and record pre/post orders.
3. Implement bidirectional BFS and compare node expansions vs. BFS on random graphs.