Graphs as Adjacency Lists, and BFS/DFS

Every tree this course has covered is, technically, a special kind of graph — one with extra rules attached (exactly one path between any two nodes, no cycles, one designated root). Drop those rules, and you get a general graph: dependency graphs, social networks, module import graphs, road networks. The genuinely good news is that almost everything from the tree section still applies — with one necessary addition.

Representing a graph: the adjacency list

A tree's children array only worked because trees have a clear parent-to-child direction. A graph's connections (called edges) can go between any two nodes, so the natural representation is a map from each node to the list of nodes it connects to:

const graph = new Map([
  ["alice", ["bob", "carol"]],
  ["bob", ["alice", "dave"]],
  ["carol", ["alice"]],
  ["dave", ["bob"]],
]);

This is an adjacency list. The alternative — an adjacency matrix, an n x n grid where matrix[i][j] = 1 if node i connects to node j — costs O(n²) space regardless of how many actual connections exist. For a sparse graph (most nodes connect to only a handful of others — the realistic case for social networks, dependency graphs, and most real-world networks), an adjacency list costs space proportional to the actual number of connections, which is typically far smaller than n². This is the same "don't pay for structure you don't have" instinct as choosing Map over an array scan in the hashing part of this course, just applied to graph structure instead of key lookup.

BFS and DFS still work — with one necessary addition

function bfsGraph(graph, start) {
  const visited = new Set([start]); // the addition trees didn't need
  const queue = [start];
  const order = [];
 
  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);
 
    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
 
  return order;
}

Compare this to the tree BFS from several lessons ago: identical shape, with exactly one addition — a visited set, checked before enqueueing a neighbor. This addition is not optional the way it was skippable for trees. A tree guarantees exactly one path to any node, so tree traversal code can never revisit a node by construction. A graph makes no such guarantee — alice connects to bob, who connects back to alice — so without tracking what's already been visited, the traversal would loop between them forever, or at minimum redundantly reprocess the same nodes many times over.

DFS gets the identical treatment:

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

Real frontend framings

Dependency graphs. A module import graph — moduleA imports moduleB and moduleC — is exactly this structure, and "which modules does building moduleA eventually depend on" is a direct DFS/BFS reachability question: start at moduleA, traverse, and every node visited is a transitive dependency.

Friend-of-friend recommendations. "People connected to someone I'm connected to, but not connected to me directly" is naturally a BFS question, for the same reason BFS suited shortest-path questions on trees: BFS visits nodes in strictly increasing distance from the start, so "everyone at distance 2" (friends of friends) is exactly the second group BFS reaches, after "everyone at distance 1" (direct friends) — no equivalent guarantee exists for DFS, which could reach a distance-2 node before a different distance-1 node depending on the order edges happen to be listed.

function friendsOfFriends(graph, start) {
  const distances = new Map([[start, 0]]);
  const queue = [start];
 
  while (queue.length > 0) {
    const node = queue.shift();
    for (const neighbor of graph.get(node) ?? []) {
      if (!distances.has(neighbor)) {
        distances.set(neighbor, distances.get(node) + 1);
        queue.push(neighbor);
      }
    }
  }
 
  return [...distances.entries()]
    .filter(([, distance]) => distance === 2)
    .map(([person]) => person);
}

What to remember

• A tree is a graph with extra guarantees (no cycles, one path between any two nodes); dropping those guarantees is the entire conceptual jump from trees to graphs.
• Adjacency lists (a map from node to its neighbors) cost space proportional to the actual number of connections — the right choice for sparse, real-world graphs, versus an adjacency matrix's fixed O(n²).
• Graph BFS/DFS need a visited set that tree traversal didn't strictly need, because graphs can have cycles or multiple paths converging on the same node — without it, traversal can loop forever or redo work.
• BFS's distance-ordered exploration is what makes "everyone at exactly distance k" (friends of friends) a natural, direct question to answer — the same shortest-path property that made BFS the right choice for trees.