Day 23: Graphs — BFS & DFS

DAY 23 / 30 · WEEK 4

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 and DFS traversal

in the queue (discovered, waiting) dequeued, checking neighbors now fully processed

BFS Traversal

BFS traversal from a starting node — each node is marked visited when enqueued, and fully processed only when dequeued.

Press Play or Step to begin.

Step 0 / 0

▶ PlayStep ⏭⟲ Reset🔀 Shuffle

DFS Traversal

on the call stack (ancestor, waiting) current call, checking neighbors now finished, returned

DFS traversal from a starting node — the recursion commits to one neighbor's whole subtree before backtracking to try the next.

Press Play or Step to begin.

Step 0 / 0

▶ PlayStep ⏭⟲ Reset🔀 Shuffle

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

Queue (before)	Dequeue	Neighbor checks	Visited set (after)
[A]	A	B new → enqueue; C new → enqueue	{A, B, C}
[B, C]	B	A visited, skip; D new → enqueue	{A, B, C, D}
[C, D]	C	A visited, skip; D visited, skip	{A, B, C, D}
[D]	D	B, C visited, skip; E new → enqueue; G new → enqueue	{A, B, C, D, E, G}
[E, G]	E	D visited, skip; F new → enqueue	{A, B, C, D, E, F, G}
[G, F]	G	D visited, skip	{A, B, C, D, E, F, G}
[F]	F	E visited, skip	{A, B, C, D, E, F, G}

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

Call stack (path from A)	Action	Visited set (after)
[A]	Visit A (start)	{A}
[A, B]	A → B unvisited, recurse	{A, B}
[A, B, D]	B → A visited skip; B → D unvisited, recurse	{A, B, D}
[A, B, D, C]	D → B, C: C unvisited, recurse (B was skipped)	{A, B, D, C}
[A, B, D]	C → A, D both visited — backtrack out of C	{A, B, D, C}
[A, B, D, E]	D → C visited skip; D → E unvisited, recurse	{A, B, D, C, E}
[A, B, D, E, F]	E → D visited skip; E → F unvisited, recurse	{..., F}
[A, B, D, E] → [A, B, D]	F → E visited — backtrack out of F, then out of E	{..., F}
[A, B, D, G]	D → G unvisited, recurse	{..., G}
[] (empty)	G, D, B, A all exhausted — backtrack all the way out	{A, B, C, D, E, F, G}

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

Operation	Time	Space	Why
BFS traversal	O(V + E)	O(V)	The visited set guarantees every vertex is enqueued and processed exactly once — O(V). Every edge is examined once from each endpoint it touches, so O(E) for undirected (O(2E), same order of growth) or O(E) for directed.
DFS traversal	O(V + E)	O(V)	Same reasoning as BFS — the visited set bounds vertex visits to V, edge checks to E. Space is the recursion depth (or explicit stack size), worst case O(V) for a graph that’s one long path.
Adjacency list (representation)	O(1) average to list a node’s neighbors	O(V + E)	Most common in interviews — compact for sparse graphs, and it’s exactly what BFS/DFS above iterate over.
Adjacency matrix (representation)	O(1) to check if a specific edge exists	O(V²)	Simple lookups for “are u and v connected”, but wastes space on sparse graphs — a graph with 1000 nodes and 2000 edges still allocates 1,000,000 matrix cells.

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

1. Find if Path Exists in Graph (Easy)

Given a graph as an edge list, a source, and a destination, return whether there’s a path from source to destination. Today’s traversal, with an early exit.

Show hint

Build an adjacency list from the edge list first (remember: undirected, so add both directions). Then run BFS or DFS from source and check whether destination ever gets visited — you can even return true the moment you dequeue/visit it.

Show solution

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;
}

2. Number of Islands (Medium)

Given a 2D grid of '1' (land) and '0' (water), count the number of islands — a grid is a graph in disguise, where each cell is a node connected to its up / down / left / right neighbors.

Show hint

Scan every cell. Whenever you find an unvisited '1', that’s a brand-new island — increment your count, then flood-fill outward from it with BFS or DFS, marking every connected land cell visited so the outer scan never counts it again. This is exactly today’s “disconnected graph” trap, applied deliberately — each island is its own connected component.

Show solution

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;
}

3. Clone Graph (Medium)

Given a reference node in a connected undirected graph, return a deep copy of the whole graph. The graph can contain cycles, so the visited set has to double as a map from original node to its clone.

Show hint

Use a Map instead of a Set for “visited” — key is the original node, value is its clone. Traverse (BFS or DFS) as usual, but the first time you see a node, create its clone and store it in the map immediately, before recursing / enqueuing into its neighbors — that’s what lets a cycle safely point back to a clone that already exists instead of cloning it twice.

Show solution

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

1. Why does graph traversal need a visited set when Day 19’s tree traversal never did?

A tree has no cycles and one path between nodes; a general graph can have cycles, so nodes can be re-reached.

• Correct! A tree is a graph with no cycles and exactly one path between any two nodes, so walking from parent to child can never loop back to an already-seen node. A general graph can have cycles and multiple paths, so without a visited set BFS/DFS can loop forever.

2. In BFS, when should a node be added to the visited set?

The moment it’s enqueued (discovered) — not when it’s later dequeued.

• Correct! Mark a node visited the moment it’s enqueued, not when it’s dequeued. Marking at dequeue time lets the same node be discovered and pushed onto the queue multiple times before it’s ever processed.

3. How do you make sure every node gets visited in a disconnected graph?

Loop over all nodes and start a new traversal from each unvisited one, not just a single starting point.

• Correct! A single BFS or DFS call only reaches nodes connected to its starting point. To cover a disconnected graph, loop over every node and start a fresh traversal from each one that’s still unvisited after the previous traversals finished.

4. What is the time complexity of BFS or DFS on a graph, and why?

O(V + E) — every vertex is visited once and every edge is examined once or twice.

• Correct! The visited set guarantees each of the V vertices is processed exactly once, and each of the E edges is examined at most twice (once from each endpoint) — giving O(V + E), not something that depends on the number of cycles.

5. For a typical sparse interview graph, which representation is the usual default, and why?

Adjacency list — O(V + E) space, and it’s exactly what BFS/DFS iterate over.

• Correct! An adjacency list uses O(V + E) space and is what’s iterated over directly in BFS/DFS — the standard, most common representation in interviews, especially for the sparse graphs those problems typically use. A matrix costs O(V²) space regardless of how many edges actually exist.