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

Graphs: BFS & DFS

A graph generalizes a tree by dropping the "no cycles, single parent" restriction, and it's usually represented as an adjacency list for traversal purposes:

function buildGraph(edges) {
  const graph = new Map();
  for (const [a, b] of edges) {
    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 — record both directions
  }
  return graph;
}

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);          // mark visited at ENQUEUE time
        queue.push(neighbor);
      }
    }
  }
  return order;
}

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

Marking a node visited at enqueue time rather than dequeue time is a deliberate, load-bearing choice in the BFS above: skip it, and the same node can get pushed onto the queue multiple times by different neighbors before it's ever processed once, wasting work and — on some graph-shaped problems — producing outright incorrect results.

BFS explores strictly level by level, which is exactly why it guarantees the shortest path by number of edges in an unweighted graph: the very first time BFS reaches a node, it has done so via the fewest possible edges, since every node one edge closer to the start was necessarily processed first. DFS gives no such guarantee — it can easily reach a node via a long, winding path first. DFS earns its keep instead on problems about full exploration where the specific order doesn't matter, or that are more naturally expressed recursively: reachability, exhaustively enumerating every path, or anything that decomposes cleanly into "explore this branch fully, then backtrack."

Connected components

function countComponents(n, edges) {
  const graph = buildGraph(edges);
  const visited = new Set();
  let components = 0;

  for (let node = 0; node < n; node++) {
    if (!visited.has(node)) {
      components++;
      dfs(graph, node, visited);        // sweeps the ENTIRE component in one call
    }
  }
  return components;
}

A traversal started from any node inside a connected component necessarily reaches every other node in that same component, and nothing outside it — that's the whole reason "loop over every node, and only start a fresh traversal when it hasn't been visited yet" correctly counts or labels components in O(V + E) total, touching every edge exactly a constant number of times.

Practice this on Code Lab: Graphs and BFS & DFS