DSA Patterns for Coding Interviews: The Techniques Behind Almost Every Problem

Part 9 of 16 · ~2 min

Graphs: BFS & DFS

Some courses at partner campuses count as equivalent to ones offered here, and those rulings chain: A ruled equivalent to B, B to C, and a transfer advisor needs to know A effectively reaches C — even with no direct ruling ever filed between them. That's a graph, and an adjacency list represents it:

function buildEquivalencyGraph(pairs) {
  const graph = new Map();
  for (const [a, b] of pairs) {
    if (!graph.has(a)) graph.set(a, []);
    if (!graph.has(b)) graph.set(b, []);
    graph.get(a).push(b);
    graph.get(b).push(a);              // undirected — a ruling runs both ways
  }
  return graph;
}

function bfsShortestChain(graph, start, target) {
  const visited = new Set([start]);
  const queue = [[start, 0]];
  while (queue.length) {
    const [code, hops] = queue.shift();
    if (code === target) return hops;
    for (const neighbor of graph.get(code) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);          // marked visited when QUEUED, not when processed
        queue.push([neighbor, hops + 1]);
      }
    }
  }
  return -1;   // no chain links them
}

function dfsAllEquivalents(graph, start, visited = new Set(), out = []) {
  visited.add(start);
  out.push(start);
  for (const neighbor of graph.get(start) || []) {
    if (!visited.has(neighbor)) dfsAllEquivalents(graph, neighbor, visited, out);
  }
  return out;
}

Marking a node visited the moment it's queued, rather than the moment it's actually processed, isn't cosmetic — skip it and the same course code can land in the queue several times through different edges before it's handled even once, burning work and, on some graphs, producing wrong answers outright.

BFS's level-by-level march is why it's guaranteed to find the shortest chain: the first time it ever reaches a node, that arrival used the fewest possible edges, because everything one hop closer got processed first. DFS makes no such promise — it might wander a long way before circling back to a near neighbor. DFS earns its place instead on "find everything reachable, order doesn't matter" jobs, like listing every course a given one is transitively equivalent to for an advisor's full picture.

Connected components

The registrar wants a standing count: across the whole catalog, how many separate clusters of mutually-equivalent courses exist?

function countEquivalencyClusters(allCodes, graph) {
  const visited = new Set();
  let clusters = 0;

  for (const code of allCodes) {
    if (!visited.has(code)) {
      clusters++;
      dfsAllEquivalents(graph, code, visited);   // one call clears out the ENTIRE cluster
    }
  }
  return clusters;
}

Start a traversal anywhere inside a cluster and it necessarily reaches every other member of that cluster and nothing outside it — which is exactly why "loop over every code, start a fresh traversal only where nothing's been visited yet" tallies every cluster correctly in O(V + E), touching each equivalency edge a fixed number of times. A course with no filed equivalency still counts — as its own cluster of one.

Practice both traversals on Graphs, or drill BFS and DFS directly.