Graphs

Graph: nodes connected by edges, with cycles and multiple paths. Always carry a visited Set or a cycle will infinite-loop your traversal. Adjacency lists are the right default.

A graph is a set of nodes connected by edges. Unlike a tree, a graph can have cycles (a chain of edges that loops back to a node you already visited) and more than one path between any two nodes. Social networks, package dependency graphs, and route maps are all graphs.

An adjacency list represents a graph as a Map where each key is a node and its value is the array of nodes it connects to. For an undirected graph you add an entry in both directions. This representation uses space proportional to the number of edges, which makes it efficient for sparse graphs where most nodes are not directly connected to each other.

const graph = new Map();
 
function addEdge(a, b) {
  if (!graph.has(a)) graph.set(a, []);
  if (!graph.has(b)) graph.set(b, []);
  graph.get(a).push(b); // undirected: add both directions
  graph.get(b).push(a);
}
 
addEdge("alice",   "bob");
addEdge("alice",   "carol");
addEdge("bob",     "dave");
addEdge("carol",   "dave");
 
// graph:
//  alice  ->  bob, carol
//  bob    ->  alice, dave
//  carol  ->  alice, dave
//  dave   ->  bob, carol
 
for (const [node, neighbors] of graph) {
  console.log(`${node}: ${neighbors.join(", ")}`);
}
// alice: bob, carol
// bob: alice, dave
// carol: alice, dave
// dave: bob, carol

Breadth-first search (BFS) explores nodes level by level using a queue. A visited Set prevents revisiting nodes; without it, any cycle in the graph turns the traversal into an infinite loop. Removing the Set from this example and adding an edge that creates a cycle shows the problem immediately.

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  visited.add(start);
 
  while (queue.length > 0) {
    const node = queue.shift(); // take from the front (FIFO)
    console.log("visited:", node);
 
    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);   // mark before enqueue to avoid duplicates
        queue.push(neighbor);
      }
    }
  }
}
 
bfs(graph, "alice");
// visited: alice
// visited: bob
// visited: carol
// visited: dave
 
// WITHOUT the visited Set, alice -> bob -> alice -> bob -> ...
// => infinite loop because the graph has a cycle (alice <-> bob)

In production

Any graph traversal needs cycle detection via a visited Set or it will infinite-loop on real data - production graphs (dependency trees, social graphs, route networks) nearly always contain cycles. Adjacency lists are the right default: they use O(nodes + edges) space, which is efficient for sparse graphs where most pairs of nodes are not directly connected. Adjacency matrices use O(nodes²) space and only beat adjacency lists when the graph is dense and you need constant-time edge lookup between arbitrary node pairs.

← PreviousTrees

Enjoyed this? Get more essays on software craft delivered to your inbox.

Subscribe free