Graphs and traversal — following the connections

You want to decide the startup order of microservices. You want to check how far a permission is inherited. You want to know where a circular import closes.

These look like different problems, but replacing them with "points and lines between them" reduces them to a single problem. Graphs are the vocabulary for that replacement.

What you'll learn in this chapter

• Graph vocabulary and choosing between adjacency list and matrix
• Why BFS gives shortest paths for unweighted graphs
• DFS and why you can't stop without a visited set
• Ordering dependencies with topological sort and detecting cycles
• The idea of treating "state" as a vertex and using search

Prerequisites

Builds on stacks and queues from Choosing data structures, and the shape of recursion from Recursion and divide-and-conquer.

Vertices and edges

A graph is made of vertices (nodes) and edges connecting vertices. Two distinctions matter.

Distinction	Meaning	Example
Directed / undirected	Does the edge have direction?	"A imports B" is directed. "A and B are friends" is undirected
Weighted / unweighted	Do edges carry cost?	"Number of transfers" is unweighted. "Travel time" is weighted

A tree is a special kind of graph. Trees in the data structures chapter are graphs with no cycles and everything connected. So code that walks trees doesn't directly work on graphs — graphs can have cycles, and handling that is required.

Two representations

// Adjacency list: per vertex, "what it connects to"
type Graph = Map<string, string[]>;

const graph: Graph = new Map([
  ["A", ["B", "C"]],
  ["B", ["A", "D"]],
  ["C", ["A", "D"]],
  ["D", ["B", "C", "E"]],
  ["E", ["D"]],
]);

The other is an adjacency matrix — a row × column table with edge presence.

	Adjacency list	Adjacency matrix
Memory	O(V + E)	O(V²)
"Is A adjacent to B?"	O(degree of A)	O(1)
"All neighbors of A"	O(degree of A)	O(V)

V is vertex count; E is edge count. Real-world graphs are usually sparse — few edges relative to vertex count — so the adjacency list is the default. Matrices win when vertices are few and edges dense, or when "is this pair adjacent" is asked in bulk.

Breadth-first search — expand from nearby

Using a queue, expand layer by layer from nearest to the source.

function bfsDistances(g: Graph, start: string): Map<string, number> {
  const dist = new Map<string, number>([[start, 0]]);
  const queue: string[] = [start];
  for (let head = 0; head < queue.length; head++) {
    const v = queue[head];
    for (const next of g.get(v) ?? []) {
      if (dist.has(next)) continue; // Already has distance = visited
      dist.set(next, (dist.get(v) as number) + 1);
      queue.push(next);
    }
  }
  return dist;
}

const d = bfsDistances(graph, "A");
console.log([...d].map(([v, n]) => `${v}=${n}`).join(" "));
// A=0 B=1 C=1 D=2 E=3

A to D has two routes — A→B→D and A→C→D — both two steps, so D=2.

Why this distance is the shortest: layers aren't skipped. The queue is FIFO, so all distance-1 vertices are processed before moving to distance 2. The first time a vertex is reached, that's the shortest distance, and later routes need no update. dist.has(next) then continue in the code is that judgment.

Depth-first search — go as far as you can

Advance as far as possible; back up one on dead ends. Recursion writes it naturally.

function dfsOrder(g: Graph, start: string): string[] {
  const seen = new Set<string>();
  const order: string[] = [];
  function visit(v: string): void {
    if (seen.has(v)) return; // Without this, cycles never stop
    seen.add(v);
    order.push(v);
    for (const next of g.get(v) ?? []) visit(next);
  }
  visit(start);
  return order;
}

console.log(dfsOrder(graph, "A").join(" -> "));
// A -> B -> D -> C -> E

A's neighbors are B and C, but after entering B you go all the way to D before coming back to C. The visit order is completely different from BFS.

Writing with recursion lets the call stack remember "where to return". Rewriting with an explicit stack — and then, as covered in Recursion and divide-and-conquer, managing the stack depth problem yourself.

Without a visited set, it doesn't stop

Both codes above have visited records. They aren't optional.

Graphs have cycles. Traversing A → B → D → C → A without visited tracking cycles forever. Reusing tree-walking code on graphs produces this shape as an infinite loop or RangeError.

Where you record visited also matters. Not recording when enqueuing means the same vertex can be enqueued multiple times. The BFS above marks visited when adding to dist, so no double-enqueue.

Complexity

Both are O(V + E). Each vertex is visited once; each edge is examined once (in undirected graphs, once from each end).

Not O(V × E). The total edge-visits are bounded by the edge count. In undirected graphs, sum of degrees equals twice the edge count, corresponding to visiting each edge from each end.

With different weights, BFS isn't shortest

BFS gives the shortest path only when all edge weights are equal.

Minimizing transfers → BFS is right. But minimizing travel time can be broken by "one long edge" being slower than "two short edges". BFS counts only hops and can't handle this inversion.

For different weights, use Dijkstra's algorithm. The rule "next to finalize is the vertex with the smallest tentative distance not yet finalized" replaces the queue with a priority queue. Negative weights need something else again.

This chapter doesn't go into implementation. Pin the boundary: equal weights → BFS, different weights → Dijkstra.

Treating states as vertices

Graphs aren't only a tool for things already given as points and lines. Treat possible states as vertices and transitions as edges, and the problem becomes a search.

Problem	Vertex	Edge
Minimum moves in a puzzle	Board	Moving one step
Change a word one letter at a time	Word	Rewrite one letter
How far permissions propagate	Role	"Inherits"

"Minimum steps" asked → BFS — that's the practical payoff of this translation. States are finite and each step has equal cost.

Watch the state count. Board combinations explode exponentially, so making them all vertices makes the search never finish. In practice, normalize states to unify duplicates, or restrict the search range.

Ordering dependencies and detecting cycles

In directed graphs, ordering "what must be finished first" is topological sort. Build order, migration application order, initialization order fit this.

// "Finish B before A" = edge from A to B
const deps: Graph = new Map([
  ["config", []],
  ["db", ["config"]],
  ["api", ["db", "config"]],
  ["web", ["api"]],
]);

function topoSort(g: Graph): string[] | null {
  const state = new Map<string, 0 | 1 | 2>(); // 0 unvisited / 1 visiting / 2 done
  const order: string[] = [];
  let cyclic = false;

  function visit(v: string): void {
    const s = state.get(v) ?? 0;
    if (s === 2) return;
    if (s === 1) { cyclic = true; return; } // Returned to a "visiting" vertex = cycle
    state.set(v, 1);
    for (const next of g.get(v) ?? []) visit(next);
    state.set(v, 2);
    order.push(v); // Push self after all dependencies finish
  }

  for (const v of g.keys()) visit(v);
  return cyclic ? null : order;
}

console.log(topoSort(deps)?.join(" -> "));
// config -> db -> api -> web

const cyclicGraph: Graph = new Map([["a", ["b"]], ["b", ["c"]], ["c", ["a"]]]);
console.log(topoSort(cyclicGraph) === null ? "cycle detected" : "no cycle");
// cycle detected

Holding visited as three values instead of two is the key. Returning to "done" is just re-visiting from another path — not a problem. Only returning to "visiting" is a cycle. A two-value flag can't distinguish these.

For instance, in an acyclic graph with a→b, a→c, b→d, c→d, d is reached via two paths. Two-value "any re-visit is a cycle" wrongly flags this graph as cyclic.

This isn't the only style. Another is to peel off "vertices with 0 incoming edges" in order. As you peel, decrement destinations' in-degree; when it hits 0, enqueue. That's the same shape as the BFS earlier. But with this chapter's edge direction (A → B means B first), in-degree 0 means "nothing depends on it", so the peeled order is the reverse of the execution order — reverse it at the end. If the output count is less than the total, there's a cycle — no three-state needed. Prefer this when avoiding deep recursion.

Cycle detection is directly useful in practice. When task dependencies can be registered by users, as the Database Design Guide's real-world cases covers, preventing cycles with database constraints is complex, so detecting them in the application layer before registration is standard.

Decision procedure

Question	Choose
Shortest steps / minimum transfers	BFS
Reachability, enumerate all paths	DFS (less memory)
Order for executing dependencies	Topological sort
Detect cycles in a directed graph	DFS with three-state, or the in-degree-peeling version needs no three-state
Shortest path with different edge costs	Dijkstra (BFS won't produce it)

Two things to decide before searching:

1. What is the vertex — the original data as-is, or a state translation
2. Where to record visited — at enqueue time or at dequeue time

Common misconceptions

"DFS also produces shortest paths." — Doesn't. The first path DFS finds is "one that didn't dead-end first" — no length guarantee. For shortest, use BFS.

"Visited tracking is for performance." — It's for correctness. In undirected or cyclic graphs, you don't terminate without it.

"Graphs are a specialized data structure." — An adjacency list is just Map<vertex, vertex[]>. Before reaching for a specialized library, check whether your data already forms a graph. Foreign-keyed tables, import statements, role inheritance — all graphs.

"Tree code can be reused for graphs." — Trees are acyclic graphs, so tree code lacks visited tracking. Applying to graphs directly won't stop.

Exercises

Q1. In a design where roles inherit "general → editor → admin", judge whether a user can perform a specific action. BFS or DFS?

Answer and explanation

Answer: Either. It's a reachability question.

"Can they do it" asks reachability, not path length. Since shortest isn't needed, BFS's advantage doesn't apply and either gives the same answer.

The basis for choice is elsewhere.

• DFS (recursion) — short code. If inheritance is shallow, natural
• BFS — no worry about the stack if depth can grow

What actually matters is visited tracking. Role inheritance can accidentally cycle by config error ("A inherits B; B inherits A"). Without visited, the moment that setting lands, the judgment loops forever.

To make judgment fast, another route is to pre-expand "the set of permissions each role can reach", so no search is needed per judgment. But this requires recomputation when inheritance changes, so choose by change frequency vs. judgment frequency.

Q2. You found "minimum number of transfers" with BFS. Can the same code find "shortest travel time" from vertex to vertex?

Answer and explanation

Answer: It cannot. Edge weights aren't equal.

BFS's shortest guarantee rests on not skipping layers. All distance-1 nodes are processed before advancing to distance-2, so first reach = shortest.

With travel time, edges have different costs. The premise fails. "One edge in 60 minutes" versus "two edges totaling 20 minutes" — an inversion BFS can't see because it only counts hops.

You need Dijkstra. Replace the queue with a priority queue and use the rule finalize the vertex with the smallest tentative distance, not yet finalized. BFS is Dijkstra's special case when all weights are 1.

Conversely, with all weights equal, BFS suffices. BFS is lighter (no priority queue), so pick it when counting transfers.

Q3. Migrations are ordered by topological sort. One day: "cannot determine order". What happened and how to investigate?

Answer and explanation

Answer: A cycle formed in dependencies. Identify by outputting the call path that returned to a "visiting" vertex.

Topological sort produces order only for acyclic directed graphs. "A before B, B before C, C before A" simultaneously has no valid order.

Investigation uses cycle detection itself. In the three-state DFS (unvisited / visiting / done), the call path at the moment of returning to a "visiting" vertex is the cycle. Beyond throwing an error, outputting the stack at that time tells you exactly which files formed the loop.

Common in practice: there are two systems for expressing dependencies. If you can write both "this migration is after X" and "X is before this migration", fixing only one leaves the directions inconsistent, creating a cycle. After detection, consolidating declaration direction prevents recurrence.

Summary

• Graphs are vertices and edges. The distinctions to keep are directed/undirected and weighted/unweighted
• A tree is an acyclic graph. Tree code applied to graphs won't stop
• Adjacency list is the default. Adjacency matrix wins for small vertex counts with dense edges
• BFS is queue-based, expands layer by layer, giving shortest paths on equal weights
• DFS uses a stack or recursion. No shortest guarantee
• Visited tracking is for correctness, not performance
• Both are O(V + E)
• Different edge costs → Dijkstra. BFS won't produce it
• Treating states as vertices turns puzzles and string problems into searches. Watch for state-space explosion
• DFS topological sort needs three-state. Only re-visits to "visiting" are cycles. The in-degree-peeling version needs no three-state

Related references

• Database Design Guide — Real-world cases — Detecting dependency cycles in the application layer
• TypeScript Design Patterns — Visitor — Design that separates traversal logic from the structure

What to read next

• Dynamic programming — What to do when the same state is computed repeatedly during search
• Choosing data structures — The stack/queue difference becomes the DFS/BFS difference