DAY 23 / 30 · WEEK 4

Graphs — BFS & DFS

Goal of the day

• Represent a graph two ways — adjacency list (the one you'll actually write in an interview) and adjacency matrix (know it exists, know its trade-off) — and see why the list wins for most real-world graphs.
• Traverse a graph with BFS (queue) and DFS (recursion), both built on the same adjacency list, and see how their visiting orders differ on the exact same graph.
• Understand why a visited set is mandatory here in a way it never was for Day 19's tree traversal — a general graph can have cycles and multiple paths between two nodes, so without tracking what's already been seen, BFS/DFS would loop forever.

Concept

A tree (Day 19) is actually a special, restricted kind of graph: no cycles, and exactly one path between any two nodes. That's precisely why tree BFS/DFS never needed to track visited nodes — walking "down" from a parent to its children could never lead back to a node you'd already seen, because there's no path back up except the one you just came from.

A general graph drops that restriction. Nodes can have multiple neighbors that lead to each other in loops — cycles — and there can be more than one path between two nodes. Think of a road map: City A connects to City B, City B connects to City C, and City C connects right back to City A. Or a social network: you're friends with Sam, Sam is friends with Priya, and Priya is friends with you too. Follow those connections without remembering where you've been, and you'll walk A → B → C → A → B → C forever — the traversal never terminates.

That's the one genuinely new idea in this lesson: a visited set (a Set or a plain object used as a hash set) that records every node the instant it's been discovered, so BFS/DFS never re-processes — and never re-queues or re-recurses into — a node twice. Everything else (the queue for BFS, the call stack or recursion for DFS) is exactly what you already know from Day 19; the visited set is the only new moving part, and it's the difference between a traversal that finishes and one that hangs forever.

Diagram: graph structure and its adjacency list

Diagram: why a cycle needs a visited set

Interactive visualization: BFS traversal

Interactive visualization: DFS traversal

The code: BFS and DFS on an adjacency list

function bfs(graph, start) {
  const visited = new Set([start]);   // mark the start visited immediately
  const queue = [start];
  const order = [];

  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);        // mark visited when ENQUEUED, not when dequeued
        queue.push(neighbor);
      }
    }
  }
  return order;
}

function dfs(graph, start, visited = new Set(), order = []) {
  visited.add(start);                  // mark visited the instant we enter
  order.push(start);
  for (const neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited, order);
    }
  }
  return order;
}

Line by line:

• bfs: visited starts with start already in it, and queue starts holding just start. Each loop iteration dequeues one node, records it in order, then scans its neighbors.
• The critical line is visited.add(neighbor) happening before queue.push(neighbor) — a node is marked visited the moment it's discovered (enqueued), not when it's finally dequeued and processed. Skipping this, or marking visited only at dequeue time, is a real bug — see the trap in Interview Corner below.
• dfs is recursive: it marks start visited and records it immediately on entry, then loops over its neighbors, recursing into any that aren't visited yet. visited and order are threaded through the recursive calls as default parameters so every call shares the same two collections instead of each getting its own empty ones.
• Both functions check graph[node] — an adjacency list, exactly the representation from the diagram above. Neither would work directly against an adjacency matrix without first converting each row into a list of neighbor indices.
• The interactive DFS visualization above simulates this exact recursion with an explicit array of call frames (one frame per node currently "on the stack") so you can watch nodes go active → wait as an ancestor → finish and pop, without needing a separate call-stack panel — the traversal order it produces is identical to calling dfs for real.

Dry run: BFS from A

BFS order: A → B → C → D → E → G → F. Notice C and D both get checked as neighbors of two different nodes (B and D check each other's territory) — without the visited set, C would enqueue D a second time, and the 4-node cycle A-B-D-C-A would never let the queue empty out.

Dry run: DFS from A

DFS order: A → B → D → C → E → F → G — a genuinely different order from BFS on the exact same graph, because DFS commits to one neighbor's whole subtree before backtracking to try the next one.

Complexity

Interview corner

• Why didn't Day 19's tree traversal need a visited set, but graph traversal does? A tree is a graph with no cycles and exactly one path between any two nodes — walking from a parent to a child can never loop back to an ancestor. A general graph drops both guarantees: cycles exist, and a node can be reached from more than one direction. Without tracking what's already been seen, BFS/DFS on a cyclic graph never terminates.
  ⚠ Trap: forgetting the visited set entirely doesn't just produce a wrong answer — on any graph with a cycle, it's an infinite loop. Always ask "does this graph guarantee no cycles?" before assuming you can skip it; if you're not certain, add the visited set.
• In BFS, does it matter whether you mark a node visited when it's ENQUEUED or when it's DEQUEUED? Yes — mark at enqueue time. If you instead wait until a node is dequeued to mark it visited, the same node can be discovered by multiple neighbors and pushed onto the queue several times before it's ever processed, wasting work and — in variants that track "distance from start" per node — potentially overwriting a correct shorter distance with a later, wrong one.
  ⚠ Trap: this is a subtle bug because the traversal still eventually terminates and often still visits every reachable node — it just does extra, wasted work, and can silently corrupt any per-node bookkeeping (like distances) that assumes each node is only ever enqueued once.
• What if the graph is disconnected — some nodes aren't reachable from your starting point at all? A single BFS or DFS call only reaches whatever's connected to its start node. To visit every node in a disconnected graph, loop over all nodes in the graph and kick off a fresh traversal from any node that's still unvisited after the previous ones finished — not just from one starting point.
  ↳ Common follow-up: "How would you count the number of separate connected components?" — count how many times you have to start a fresh traversal from an unvisited node; that count is the number of components.
• When would you reach for an adjacency matrix instead of an adjacency list? When the graph is dense (edge count close to V²) or you need O(1) "is there an edge between u and v" checks and can afford O(V²) space. For the sparse graphs typical of interview problems (grids, small explicit graphs), the adjacency list's O(V + E) space is almost always the better default.
• BFS or DFS — how do you pick? If you need the shortest path in an unweighted graph, or need to explore level by level, BFS is the right shape (more on this Day 24). If you just need to know reachability, explore every path, or the recursion naturally matches the problem (e.g. flood fill, counting components, cloning a graph), DFS is usually simpler to write and uses less peak memory on a wide, shallow graph.

How to talk through it out loud: name the representation first — "I'll model this as an adjacency list, node to array of neighbors" — then name the traversal and its engine — "BFS with a queue" or "DFS with recursion" — and immediately say the visited-set rule out loud: "I'll mark each node visited the moment I discover it, not when I finish processing it, so I never enqueue or recurse into the same node twice even if the graph has cycles." Interviewers on a graph problem are listening specifically for whether you treat the visited set as a first-class, load-bearing part of the algorithm — not an afterthought bolted on after your code infinite-loops on their test case.

Practice problems

function validPath(n, edges, source, destination) {
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  const visited = new Set([source]);
  const queue = [source];
  while (queue.length > 0) {
    const node = queue.shift();
    if (node === destination) return true;
    for (const neighbor of adj[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return false;
}

function numIslands(grid) {
  const rows = grid.length, cols = grid[0].length;
  const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
  let count = 0;

  function floodFill(r, c) {
    const queue = [[r, c]];
    visited[r][c] = true;
    while (queue.length > 0) {
      const [row, col] = queue.shift();
      const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
      for (const [dr, dc] of dirs) {
        const nr = row + dr, nc = col + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc] && grid[nr][nc] === '1') {
          visited[nr][nc] = true;
          queue.push([nr, nc]);
        }
      }
    }
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1' && !visited[r][c]) {
        count++;
        floodFill(r, c);
      }
    }
  }
  return count;
}

function cloneGraph(node) {
  if (!node) return null;
  const visited = new Map(); // original node -> its clone

  function walk(n) {
    if (visited.has(n)) return visited.get(n);
    const clone = new Node(n.val);
    visited.set(n, clone);       // store the clone BEFORE recursing — breaks the cycle
    for (const neighbor of n.neighbors) {
      clone.neighbors.push(walk(neighbor));
    }
    return clone;
  }

  return walk(node);
}

Quiz