Graphs

Things Connected to Things
Graph Vocabulary
Adjacency List or Matrix
Building the Graph Class
Breadth-First Search
Depth-First Search
Shortest Path When Every Edge Costs the Same
Connected Components
Cycles and Topological Sort
Dijkstra: Shortest Path With Weights
Interview Problems on Grids and Prerequisites
Recipe: graph.ts for algolab
Try It Yourself

1. Things Connected to Things

A tree is a strict kind of structure: one root, one path to every node. Real life is messier. Friends know friends who know each other. A road network has loops. A cell phone map has towers that connect in many directions. A package depends on other packages, which depend on others.

When "things" are connected to other "things" in any pattern at all, you have a graph. Graphs are the most general data structure in this series. A tree, a linked list, and even an array can be seen as special cases of one.

Where you meet graphs at work:

Maps and routes. Cities are the dots, roads are the lines. "Fastest way from Kep to Battambang" is a graph question.
Social networks. People are the dots, friendships are the lines. "People you may know" means friends of friends.
Dependencies. npm install reads a graph of packages that need other packages. Build tools, spreadsheets (a cell depends on other cells), and database migrations all need to know what must run first.
Networks. Routers, servers, and microservices that call each other.
State machines and workflows. An order moves from "placed" to "paid" to "shipped". Every state is a dot and every allowed move is a line.
Recommendations. "Users who bought this also bought..." is a graph between users and products.

In this chapter you learn the vocabulary, two ways to store a graph, the two core searches (BFS and DFS), and three problems that come up again and again: shortest path, "what order should I do these in?", and "what is the cheapest route?".

2. Graph Vocabulary

A graph has two ingredients:

Vertices (also called nodes): the things. Singular is vertex.
Edges: the connections between two vertices.

   Kratie --- Kampong Cham --- Phnom Penh --- Siem Reap
                                  |               |
                                Kampot        Battambang
                                  |
                                 Kep

A few words to know:

Word	Meaning
Undirected	An edge works both ways. If A is a friend of B, B is a friend of A.
Directed	An edge has a direction, drawn as an arrow. "A follows B" does not mean B follows A.
Weighted	Each edge carries a number: a distance, a cost, a time.
Neighbors	Vertices directly connected to a given vertex.
Path	A sequence of vertices where each consecutive pair is joined by an edge.
Cycle	A path that comes back to where it started.
Connected	You can get from any vertex to any other by some path.
Degree	How many edges touch a vertex (directed graphs split this into in-degree and out-degree).
DAG	A directed acyclic graph: arrows only, and no cycles. Task dependencies are DAGs.

Notice the connection with the last chapter. A tree is a connected graph with no cycles (and, when drawn with a root, with directions pointing down). Once you allow cycles, you must also remember which vertices you have already visited, or your search will go around in circles forever. This is the one big difference between walking a tree and walking a graph, and it shows up in every algorithm below as a seen set.

3. Adjacency List or Matrix

How do you store a graph in memory? There are two classic answers.

Adjacency matrix. A grid with one row and one column per vertex. The cell at row i, column j is 1 (or the weight) if there is an edge from i to j, otherwise 0. For three vertices A, B, C where A-B and B-C are connected:

const names = ["A", "B", "C"];
const matrix = names.map(() => names.map(() => 0));

matrix[0][1] = matrix[1][0] = 1; // A - B
matrix[1][2] = matrix[2][1] = 1; // B - C

console.log(matrix);
// [ [ 0, 1, 0 ], [ 1, 0, 1 ], [ 0, 1, 0 ] ]

Adjacency list. For each vertex, keep a list of its neighbors. In TypeScript, a Map from a vertex to its neighbors is perfect:

const list = new Map<string, string[]>([
  ["A", ["B"]],
  ["B", ["A", "C"]],
  ["C", ["B"]],
]);

Which to use? It depends on how many edges there are compared with vertices (V vertices, E edges):

	Adjacency list	Adjacency matrix
Memory	O(V + E)	O(V²)
Is there an edge from A to B?	O(degree of A), or O(1) with a `Map` of `Map`s	O(1)
List all neighbors of A	O(degree of A)	O(V)
Add a vertex	O(1)	O(V²) to rebuild
Best for	Sparse graphs (few edges)	Dense graphs (almost all pairs connected)

Most real graphs are sparse. A social network with a billion people does not have a billion friends each. A matrix for a million vertices needs a trillion cells, mostly zeros, while the list stores only the edges that exist. That is why the adjacency list is the default, and why we build it in the next section. Use the matrix when the graph is small and dense, or when you must test "is A connected to B?" extremely often.

4. Building the Graph Class

We store the graph as a Map from each vertex to a second Map that holds its neighbors and the weight of each edge. Using a Map for the neighbors gives O(1) "is there an edge?" checks, and the weight slot lets one class handle both weighted and unweighted graphs (unweighted edges just get weight 1).

class Graph<T = string> {
  private adjacency = new Map<T, Map<T, number>>();

  constructor(private directed = false) {}

  addVertex(vertex: T): void {
    if (!this.adjacency.has(vertex)) this.adjacency.set(vertex, new Map());
  }

  addEdge(from: T, to: T, weight = 1): void {
    this.addVertex(from);
    this.addVertex(to);
    this.adjacency.get(from)!.set(to, weight);
    if (!this.directed) this.adjacency.get(to)!.set(from, weight);
  }

  hasEdge(from: T, to: T): boolean {
    return this.adjacency.get(from)?.has(to) ?? false;
  }

  vertices(): T[] {
    return [...this.adjacency.keys()];
  }

  neighbors(vertex: T): T[] {
    return [...(this.adjacency.get(vertex)?.keys() ?? [])];
  }
}

A few details worth reading slowly:

Graph<T = string> is a generic with a default. Write new Graph() and vertices are strings. Write new Graph<number>() and they are numbers. Anything that works as a Map key can be a vertex.
new Graph(true) makes a directed graph. The default is undirected, where addEdge records the connection in both directions.
addEdge creates the vertices on demand, so you never need to call addVertex first (but you can, to add a vertex that has no edges yet).
The ! after .get(from) is safe because we just added the vertex on the line above.

Let's build a tiny road map of Cambodia (made-up connections for practice):

const roads = new Graph();
roads.addEdge("Phnom Penh", "Kampong Cham");
roads.addEdge("Phnom Penh", "Kampot");
roads.addEdge("Phnom Penh", "Siem Reap");
roads.addEdge("Kampong Cham", "Kratie");
roads.addEdge("Siem Reap", "Battambang");
roads.addEdge("Kampot", "Kep");

console.log(roads.neighbors("Phnom Penh"));
// [ 'Kampong Cham', 'Kampot', 'Siem Reap' ]
console.log(roads.hasEdge("Kep", "Kampot")); // true

The cost of storing the graph is O(V + E) memory, and addEdge is O(1). Now to the interesting part: searching it.

5. Breadth-First Search

Breadth-first search (BFS) explores a graph in rings. First the start vertex. Then all its neighbors (one step away). Then all of their neighbors (two steps away), and so on. It is the same level-by-level idea you saw for trees, with one addition: a seen set so no vertex is added twice.

BFS needs a queue (first in, first out), which is what makes it go ring by ring. We will use a plain array with a head index instead of shift(). As you learned in the Arrays and Strings chapter, shift() can be O(n), while moving an index forward is O(1). (You could also use the Queue you built in Stacks and Queues.)

bfs(start: T): T[] {
  if (!this.adjacency.has(start)) return [];

  const order: T[] = [];
  const seen = new Set<T>([start]);
  const queue: T[] = [start];

  for (let head = 0; head < queue.length; head++) {
    const vertex = queue[head];
    order.push(vertex);

    for (const next of this.neighbors(vertex)) {
      if (!seen.has(next)) {
        seen.add(next); // mark when you ADD it, not when you visit it
        queue.push(next);
      }
    }
  }
  return order;
}

Run it on the road map:

console.log(roads.bfs("Phnom Penh").join(", "));
// Phnom Penh, Kampong Cham, Kampot, Siem Reap, Kratie, Kep, Battambang

Look at the ring pattern. Phnom Penh is step 0. Its three neighbors are step 1. Kratie, Kep, and Battambang are step 2, and they come last.

One detail matters a lot: we mark a vertex as seen at the moment we add it to the queue, not when we take it out. If we waited until taking it out, two vertices could both queue the same neighbor before either is processed, and the neighbor would be queued twice. On a big graph that can turn a fast algorithm into a very slow one.

Cost: each vertex is queued once and each edge is looked at once (twice in an undirected graph), so BFS is O(V + E) time and O(V) memory.

6. Depth-First Search

Depth-first search (DFS) does the opposite: go as far as you can down one path, and only when stuck, back up and try another. It is the graph version of the tree DFS from the last chapter, with the same seen set to avoid loops. The recursive version is short:

dfs(start: T): T[] {
  const order: T[] = [];
  const seen = new Set<T>();

  const visit = (vertex: T): void => {
    seen.add(vertex);
    order.push(vertex);
    for (const next of this.neighbors(vertex)) {
      if (!seen.has(next)) visit(next);
    }
  };

  if (this.adjacency.has(start)) visit(start);
  return order;
}

console.log(roads.dfs("Phnom Penh").join(", "));
// Phnom Penh, Kampong Cham, Kratie, Kampot, Kep, Siem Reap, Battambang

Compare the two outputs. BFS jumped across: all three neighbors of Phnom Penh before anything else. DFS dived: Phnom Penh, then Kampong Cham, then straight on to Kratie (a dead end), then back to try Kampot and onward to Kep, and so on. It uses the call stack as its memory, the same way as tree DFS, so a very long chain (one million vertices in a line) can cause a stack overflow. You can replace the recursion with an explicit stack array when that is a risk.

Both searches cost O(V + E). So when do you pick which?

Question	Use
Fewest steps from A to B	BFS
Everything within N steps of A (friends of friends)	BFS
Is B reachable from A at all?	Either
Explore every possibility, e.g. solve a maze or a puzzle, then back up	DFS
Detect a cycle, order tasks, find components	DFS (or BFS-based methods)
Graph is very deep and skinny	BFS (avoids deep recursion)
Graph is very wide	DFS (a BFS queue could hold huge rings)

If you remember one rule: "shortest path by number of edges" means BFS.

7. Shortest Path When Every Edge Costs the Same

Because BFS visits vertices in order of distance, the first time it reaches a vertex, it has found a shortest path to it. To get the actual path (not just the order), remember who discovered whom. Then walk backwards from the target to the start.

shortestPath(from: T, to: T): T[] | null {
  if (!this.adjacency.has(from) || !this.adjacency.has(to)) return null;

  const cameFrom = new Map<T, T | null>([[from, null]]);
  const queue: T[] = [from];

  for (let head = 0; head < queue.length; head++) {
    const vertex = queue[head];
    if (vertex === to) break; // found it: no need to look further

    for (const next of this.neighbors(vertex)) {
      if (!cameFrom.has(next)) {
        cameFrom.set(next, vertex);
        queue.push(next);
      }
    }
  }

  if (!cameFrom.has(to)) return null; // never reached

  const path: T[] = [];
  for (
    let v: T | null | undefined = to;
    v !== null && v !== undefined;
    v = cameFrom.get(v)
  ) {
    path.push(v);
  }
  return path.reverse();
}

The cameFrom map does double duty: it is the seen set (a vertex is seen if it has an entry) and the breadcrumb trail. The start has null, which stops the walk back.

console.log(roads.shortestPath("Kep", "Battambang")?.join(" -> "));
// Kep -> Kampot -> Phnom Penh -> Siem Reap -> Battambang

console.log(roads.shortestPath("Kep", "Nowhere"));
// null

Four edges is the fewest possible hops from Kep to Battambang on this map. Real map apps use more than hop counts, since a 4-hop trip over bad roads beats nothing but loses to a 5-hop trip on a highway. That needs weights, covered in section 10.

This also answers the classic "six degrees of separation" idea: BFS from one person finds the shortest chain of friends to anyone else.

8. Connected Components

In an undirected graph, a connected component is a group of vertices that can all reach each other, with no connection to the rest. Think of separate friend groups in a school that never talk to each other, or islands.

To find them: take any vertex, BFS from it, and everything it reaches is one component. Then take any vertex not yet seen, and repeat.

connectedComponents(): T[][] {
  const seen = new Set<T>();
  const groups: T[][] = [];

  for (const vertex of this.vertices()) {
    if (seen.has(vertex)) continue;
    const group = this.bfs(vertex);
    for (const v of group) seen.add(v);
    groups.push(group);
  }
  return groups;
}

const g = new Graph();
g.addEdge("a", "b");
g.addEdge("c", "d");
g.addEdge("d", "e");
g.addVertex("f"); // alone

console.log(g.connectedComponents());
// [ [ 'a', 'b' ], [ 'c', 'd', 'e' ], [ 'f' ] ]

Each vertex is visited once overall, so the total cost is O(V + E). Uses include grouping duplicate accounts, finding clusters of related documents, and checking whether a network is split into pieces. In the next chapter you will see a faster tool for repeated "are these two connected?" questions, called union-find.

9. Cycles and Topological Sort

Now directed graphs. Say you have a build pipeline:

install --> build --> test --> deploy
lint -----> build
build --------------------> deploy

An arrow A -> B means "A must happen before B". What order can you run the steps in? Any order where every arrow points forward works. Such an order is a topological sort, and it exists exactly when the graph has no cycle. (If deploy had to come before install, you would be stuck forever. Nothing could go first.)

Cycle detection. In a directed graph, a cycle is found with DFS and three states per vertex: not visited, visiting (currently on the path we are exploring), and done. If we ever reach a vertex that is still "visiting", we have walked in a loop:

hasCycle(): boolean {
  const state = new Map<T, "visiting" | "done">();

  const visit = (vertex: T): boolean => {
    state.set(vertex, "visiting");
    for (const next of this.neighbors(vertex)) {
      const s = state.get(next);
      if (s === "visiting") return true; // back to a vertex on our path
      if (s === undefined && visit(next)) return true;
    }
    state.set(vertex, "done");
    return false;
  };

  for (const vertex of this.vertices()) {
    if (!state.has(vertex) && visit(vertex)) return true;
  }
  return false;
}

Why not just use a seen set? Because in a directed graph, reaching an already-seen vertex is not always a cycle. If two paths lead to the same vertex (A to C and B to C), C is "seen" the second time, yet there is no loop. Only reaching a vertex that is still on the current path proves a cycle. (For undirected graphs the rule is different: a cycle is an edge to a seen vertex that is not the one you just came from.)

Topological sort (Kahn's algorithm). There is a satisfying way to produce the order using BFS:

Count each vertex's incoming edges (how many things must happen before it).
Everything with 0 incoming edges is ready now. Put those in a queue.
Take one from the queue and output it. "Complete" it by removing its outgoing edges, so each neighbor's count goes down by one. If a neighbor's count reaches 0, it is now ready, so queue it.
If you output every vertex, you are done. If some are left over, they are stuck in a cycle.

topologicalSort(): T[] | null {
  const incoming = new Map<T, number>();
  for (const v of this.vertices()) incoming.set(v, 0);
  for (const v of this.vertices()) {
    for (const next of this.neighbors(v)) {
      incoming.set(next, incoming.get(next)! + 1);
    }
  }

  const ready: T[] = this.vertices().filter((v) => incoming.get(v) === 0);
  const order: T[] = [];

  for (let head = 0; head < ready.length; head++) {
    const vertex = ready[head];
    order.push(vertex);
    for (const next of this.neighbors(vertex)) {
      const left = incoming.get(next)! - 1;
      incoming.set(next, left);
      if (left === 0) ready.push(next);
    }
  }

  return order.length === this.adjacency.size ? order : null;
}

Try it on the pipeline:

const tasks = new Graph(true);
tasks.addEdge("install", "build");
tasks.addEdge("lint", "build");
tasks.addEdge("build", "test");
tasks.addEdge("build", "deploy");
tasks.addEdge("test", "deploy");

console.log(tasks.topologicalSort());
// [ 'install', 'lint', 'build', 'test', 'deploy' ]
console.log(tasks.hasCycle()); // false

tasks.addEdge("deploy", "install"); // now deploy must precede install
console.log(tasks.topologicalSort()); // null
console.log(tasks.hasCycle());        // true

Trace the first call. install and lint have 0 incoming edges, so they go first. Finishing both drops build from 2 incoming to 0. Then build is output, which makes test ready (0) and lowers deploy from 2 to 1. test is output next, and deploy reaches 0 and comes last.

Several valid orders can exist (lint before install works too). A topological sort returns one of them. This is exactly what package managers do to decide install order, what build systems like Make and Bazel do, and how a spreadsheet decides which cells to recalculate first. Both hasCycle and topologicalSort cost O(V + E).

10. Dijkstra: Shortest Path With Weights

BFS finds the path with the fewest edges. But when edges have costs (kilometers, minutes, dollars), the fewest edges is not the cheapest.

        4
   A -------- B
    \        / \
   1 \    2 /   \ 1
      \    /     \
        C -------- D
             5

Roads with their lengths in kilometers:

const km = new Graph();
km.addEdge("A", "B", 4);
km.addEdge("A", "C", 1);
km.addEdge("C", "B", 2);
km.addEdge("B", "D", 1);
km.addEdge("C", "D", 5);

To go from A to B, the direct road costs 4. But A -> C -> B costs 1 + 2 = 3, which is cheaper even though it takes two hops. BFS would pick the direct road. We need Dijkstra's algorithm (say "DYKE-struh"), invented in 1956 by Edsger Dijkstra.

The idea: always settle the cheapest unsettled vertex next. Keep a priority queue of [vertex, costSoFar] pairs. Pop the cheapest. If we already settled that vertex with a lower cost, skip it. Otherwise record its cost as final, then push each neighbor with the cost of getting there through this vertex. This is where the PriorityQueue from the last chapter earns its keep.

import { PriorityQueue } from "./priority-queue.ts";

dijkstra(start: T): Map<T, number> {
  const best = new Map<T, number>();
  const queue = new PriorityQueue<[T, number]>((a, b) => a[1] - b[1]);
  queue.push([start, 0]);

  while (!queue.isEmpty()) {
    const [vertex, cost] = queue.pop() as [T, number];
    if (best.has(vertex)) continue; // already settled with a cheaper cost

    best.set(vertex, cost);
    for (const [next, weight] of this.adjacency.get(vertex) ?? []) {
      if (!best.has(next)) queue.push([next, cost + weight]);
    }
  }
  return best;
}

Run it:

console.log(km.dijkstra("A"));
// Map(4) { 'A' => 0, 'C' => 1, 'B' => 3, 'D' => 4 }

The cheapest cost to D is 4: A -> C -> B -> D is 1 + 2 + 1. Here is the queue, step by step:

pop (A, 0): settle A=0. Push (B, 4) and (C, 1).
pop (C, 1): settle C=1. Push (B, 3) and (D, 6).
pop (B, 3): settle B=3. Push (D, 4).
pop (B, 4): B is already settled. Skip.
pop (D, 4): settle D=4.
pop (D, 6): D is already settled. Skip.

Notice that B went into the queue twice, with costs 4 and 3. Our heap cannot change an item's priority once pushed (this was exercise 7 of the last chapter), so we push a new, better copy and skip the stale one when it eventually comes out. That is why the if (best.has(vertex)) continue line is there.

Why does this work? The first time a vertex is popped, its cost is the smallest in the whole queue. Any other route to it would have to pass through a vertex that costs the same or more, and adding more edges cannot make it cheaper, as long as no edge has a negative weight. That is Dijkstra's one big rule. With negative weights you need a different algorithm (Bellman-Ford). Vertices that cannot be reached are simply missing from the result:

km.addVertex("Z");
console.log(km.dijkstra("A").has("Z")); // false

The cost is O((V + E) log V), since each edge may push one item (log cost) and each vertex is settled once. Without a heap (scanning for the cheapest each time) it would be O(V²).

To also recover the path (not only the cost), keep a cameFrom map as in section 7, updating it when you push a better route. GPS navigation uses Dijkstra's idea (usually with a speed-up called A*, which adds a "which direction is the goal" hint to the priority).

11. Interview Problems on Grids and Prerequisites

Many graph problems do not look like graphs. Learning to spot the hidden graph is half the skill. Ask: what are the vertices, and what are the edges?

Number of islands. A grid of "1" (land) and "0" (water). Count the islands, where an island is land connected up, down, left, or right.

const grid = [
  ["1", "1", "0", "0"],
  ["1", "0", "0", "1"],
  ["0", "0", "1", "1"],
  ["0", "0", "0", "0"],
];

function countIslands(grid: string[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const seen = new Set<string>();
  let islands = 0;

  const sink = (r: number, c: number): void => {
    if (r < 0 || c < 0 || r >= rows || c >= cols) return;
    if (grid[r][c] === "0" || seen.has(`${r},${c}`)) return;
    seen.add(`${r},${c}`);
    sink(r + 1, c);
    sink(r - 1, c);
    sink(r, c + 1);
    sink(r, c - 1);
  };

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "1" && !seen.has(`${r},${c}`)) {
        islands++; // a new, unseen piece of land: a new island
        sink(r, c); // mark all of it as seen
      }
    }
  }
  return islands;
}

console.log(countIslands(grid)); // 2

Here each cell is a vertex and each pair of touching land cells is an edge, so this is "count the connected components" from section 8, written as DFS over a grid. Notice there is no Graph object at all. The grid is the graph, and (r + 1, c), (r - 1, c), (r, c + 1), and (r, c - 1) are the neighbors. The cost is O(rows × cols).

Course schedule. There are count courses numbered 0 to count - 1. Each pair [course, before] means you must take before first. Can you finish all of them? This is "does the dependency graph have a cycle?", which our topologicalSort answers:

function canFinish(count: number, prerequisites: [number, number][]): boolean {
  const g = new Graph<number>(true);
  for (let i = 0; i < count; i++) g.addVertex(i);
  for (const [course, before] of prerequisites) g.addEdge(before, course);
  return g.topologicalSort() !== null;
}

console.log(canFinish(2, [[1, 0]]));         // true  (take 0, then 1)
console.log(canFinish(2, [[1, 0], [0, 1]])); // false (each needs the other)

Shortest path in a maze. S is the start, E is the exit, # is a wall. How many steps is the shortest way out? Fewest steps on an unweighted grid is a job for BFS:

function shortestMaze(maze: string[]): number {
  const rows = maze.length;
  const cols = maze[0].length;
  let start = [0, 0];
  let end = [0, 0];

  maze.forEach((row, r) =>
    [...row].forEach((ch, c) => {
      if (ch === "S") start = [r, c];
      if (ch === "E") end = [r, c];
    }),
  );

  const dist = new Map<string, number>([[start.join(), 0]]);
  const queue = [start];

  for (let head = 0; head < queue.length; head++) {
    const [r, c] = queue[head];
    const here = dist.get(`${r},${c}`)!;
    if (r === end[0] && c === end[1]) return here;

    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      const nr = r + dr;
      const nc = c + dc;
      const key = `${nr},${nc}`;
      if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
      if (maze[nr][nc] === "#" || dist.has(key)) continue;
      dist.set(key, here + 1);
      queue.push([nr, nc]);
    }
  }
  return -1; // no way out
}

console.log(shortestMaze(["S.#.", "..#E", "...."])); // 6
console.log(shortestMaze(["S#E"]));                  // -1

In the first maze, the wall in column 2 forces you down to the bottom row and back up: down, down, right, right, right, up is 6 steps. In the second maze the wall completely blocks the way, so the answer is -1.

A checklist for any graph problem:

What are the vertices? What are the edges? Directed or not? Weighted or not?
Do I need fewest steps (BFS), cheapest cost (Dijkstra), everything reachable (BFS or DFS), an ordering (topological sort), or groups (components)?
Do I need a seen set so I do not loop forever? (Yes, nearly always.)

12. Recipe: graph.ts for algolab

Create src/graph.ts in algolab. It imports the PriorityQueue from the previous chapter:

import { PriorityQueue } from "./priority-queue.ts";

export class Graph<T = string> {
  private adjacency = new Map<T, Map<T, number>>();

  constructor(private directed = false) {}

  addVertex(vertex: T): void {
    if (!this.adjacency.has(vertex)) this.adjacency.set(vertex, new Map());
  }

  addEdge(from: T, to: T, weight = 1): void {
    this.addVertex(from);
    this.addVertex(to);
    this.adjacency.get(from)!.set(to, weight);
    if (!this.directed) this.adjacency.get(to)!.set(from, weight);
  }

  hasEdge(from: T, to: T): boolean {
    return this.adjacency.get(from)?.has(to) ?? false;
  }

  vertices(): T[] {
    return [...this.adjacency.keys()];
  }

  neighbors(vertex: T): T[] {
    return [...(this.adjacency.get(vertex)?.keys() ?? [])];
  }

  // Visit everything reachable from start, nearest first.
  bfs(start: T): T[] {
    if (!this.adjacency.has(start)) return [];
    const order: T[] = [];
    const seen = new Set<T>([start]);
    const queue: T[] = [start];
    for (let head = 0; head < queue.length; head++) {
      const vertex = queue[head];
      order.push(vertex);
      for (const next of this.neighbors(vertex)) {
        if (!seen.has(next)) {
          seen.add(next);
          queue.push(next);
        }
      }
    }
    return order;
  }

  // Visit everything reachable from start, going as deep as possible first.
  dfs(start: T): T[] {
    const order: T[] = [];
    const seen = new Set<T>();
    const visit = (vertex: T): void => {
      seen.add(vertex);
      order.push(vertex);
      for (const next of this.neighbors(vertex)) {
        if (!seen.has(next)) visit(next);
      }
    };
    if (this.adjacency.has(start)) visit(start);
    return order;
  }

  // Fewest-edges path from a to b, or null if b is unreachable.
  shortestPath(from: T, to: T): T[] | null {
    if (!this.adjacency.has(from) || !this.adjacency.has(to)) return null;
    const cameFrom = new Map<T, T | null>([[from, null]]);
    const queue: T[] = [from];
    for (let head = 0; head < queue.length; head++) {
      const vertex = queue[head];
      if (vertex === to) break;
      for (const next of this.neighbors(vertex)) {
        if (!cameFrom.has(next)) {
          cameFrom.set(next, vertex);
          queue.push(next);
        }
      }
    }
    if (!cameFrom.has(to)) return null;
    const path: T[] = [];
    for (
      let v: T | null | undefined = to;
      v !== null && v !== undefined;
      v = cameFrom.get(v)
    ) {
      path.push(v);
    }
    return path.reverse();
  }

  // Groups of vertices that can reach each other (undirected graphs).
  connectedComponents(): T[][] {
    const seen = new Set<T>();
    const groups: T[][] = [];
    for (const vertex of this.vertices()) {
      if (seen.has(vertex)) continue;
      const group = this.bfs(vertex);
      for (const v of group) seen.add(v);
      groups.push(group);
    }
    return groups;
  }

  // Directed graphs: is there a loop you can follow forever?
  hasCycle(): boolean {
    const state = new Map<T, "visiting" | "done">();
    const visit = (vertex: T): boolean => {
      state.set(vertex, "visiting");
      for (const next of this.neighbors(vertex)) {
        const s = state.get(next);
        if (s === "visiting") return true;
        if (s === undefined && visit(next)) return true;
      }
      state.set(vertex, "done");
      return false;
    };
    for (const vertex of this.vertices()) {
      if (!state.has(vertex) && visit(vertex)) return true;
    }
    return false;
  }

  // Directed graphs: an order where every edge points forward.
  // Returns null when a cycle makes that impossible.
  topologicalSort(): T[] | null {
    const incoming = new Map<T, number>();
    for (const v of this.vertices()) incoming.set(v, 0);
    for (const v of this.vertices()) {
      for (const next of this.neighbors(v)) {
        incoming.set(next, incoming.get(next)! + 1);
      }
    }
    const ready: T[] = this.vertices().filter((v) => incoming.get(v) === 0);
    const order: T[] = [];
    for (let head = 0; head < ready.length; head++) {
      const vertex = ready[head];
      order.push(vertex);
      for (const next of this.neighbors(vertex)) {
        const left = incoming.get(next)! - 1;
        incoming.set(next, left);
        if (left === 0) ready.push(next);
      }
    }
    return order.length === this.adjacency.size ? order : null;
  }

  // Cheapest total weight from start to every reachable vertex.
  // Weights must not be negative.
  dijkstra(start: T): Map<T, number> {
    const best = new Map<T, number>();
    const queue = new PriorityQueue<[T, number]>((a, b) => a[1] - b[1]);
    queue.push([start, 0]);
    while (!queue.isEmpty()) {
      const [vertex, cost] = queue.pop() as [T, number];
      if (best.has(vertex)) continue; // already settled with a cheaper cost
      best.set(vertex, cost);
      for (const [next, weight] of this.adjacency.get(vertex) ?? []) {
        if (!best.has(next)) queue.push([next, cost + weight]);
      }
    }
    return best;
  }
}

Now the tests, in src/graph.test.ts:

import { test } from "node:test";
import assert from "node:assert/strict";
import { Graph } from "./graph.ts";

function cambodia(): Graph {
  const g = new Graph();
  g.addEdge("Phnom Penh", "Kampong Cham");
  g.addEdge("Phnom Penh", "Kampot");
  g.addEdge("Phnom Penh", "Siem Reap");
  g.addEdge("Kampong Cham", "Kratie");
  g.addEdge("Siem Reap", "Battambang");
  g.addEdge("Kampot", "Kep");
  return g;
}

test("undirected edges go both ways", () => {
  const g = new Graph();
  g.addEdge("A", "B");
  assert.equal(g.hasEdge("A", "B"), true);
  assert.equal(g.hasEdge("B", "A"), true);
});

test("directed edges go one way", () => {
  const g = new Graph(true);
  g.addEdge("A", "B");
  assert.equal(g.hasEdge("A", "B"), true);
  assert.equal(g.hasEdge("B", "A"), false);
});

test("bfs visits nearest first, dfs goes deep first", () => {
  const g = cambodia();
  assert.deepEqual(g.bfs("Phnom Penh"), [
    "Phnom Penh", "Kampong Cham", "Kampot", "Siem Reap",
    "Kratie", "Kep", "Battambang",
  ]);
  assert.deepEqual(g.dfs("Phnom Penh"), [
    "Phnom Penh", "Kampong Cham", "Kratie", "Kampot",
    "Kep", "Siem Reap", "Battambang",
  ]);
});

test("shortestPath finds the fewest hops", () => {
  const g = cambodia();
  assert.deepEqual(g.shortestPath("Kep", "Battambang"), [
    "Kep", "Kampot", "Phnom Penh", "Siem Reap", "Battambang",
  ]);
  assert.equal(g.shortestPath("Kep", "Nowhere"), null);
});

test("connectedComponents groups separate islands", () => {
  const g = new Graph();
  g.addEdge("a", "b");
  g.addEdge("c", "d");
  g.addEdge("d", "e");
  g.addVertex("f");
  assert.deepEqual(g.connectedComponents(), [["a", "b"], ["c", "d", "e"], ["f"]]);
});

test("topologicalSort orders tasks and detects cycles", () => {
  const g = new Graph(true);
  g.addEdge("install", "build");
  g.addEdge("lint", "build");
  g.addEdge("build", "test");
  g.addEdge("build", "deploy");
  g.addEdge("test", "deploy");
  assert.deepEqual(g.topologicalSort(), [
    "install", "lint", "build", "test", "deploy",
  ]);
  assert.equal(g.hasCycle(), false);

  g.addEdge("deploy", "install");
  assert.equal(g.topologicalSort(), null);
  assert.equal(g.hasCycle(), true);
});

test("dijkstra finds the cheapest route, not the fewest hops", () => {
  const g = new Graph();
  g.addEdge("A", "B", 4);
  g.addEdge("A", "C", 1);
  g.addEdge("C", "B", 2);
  g.addEdge("B", "D", 1);
  g.addEdge("C", "D", 5);
  g.addVertex("Z");

  const best = g.dijkstra("A");
  assert.equal(best.get("B"), 3);
  assert.equal(best.get("D"), 4);
  assert.equal(best.has("Z"), false);
});

Run them:

npx tsx --test

Add the export to src/index.ts:

export * from "./graph.ts";

Then create demo-graph.ts in the project root:

import { Graph } from "./src/graph.ts";

const g = new Graph();
g.addEdge("Phnom Penh", "Kampong Cham");
g.addEdge("Phnom Penh", "Kampot");
g.addEdge("Phnom Penh", "Siem Reap");
g.addEdge("Kampong Cham", "Kratie");
g.addEdge("Siem Reap", "Battambang");
g.addEdge("Kampot", "Kep");

console.log("bfs:", g.bfs("Phnom Penh").join(", "));
console.log("dfs:", g.dfs("Phnom Penh").join(", "));
console.log("path:", g.shortestPath("Kep", "Battambang")?.join(" -> "));

const tasks = new Graph(true);
tasks.addEdge("install", "build");
tasks.addEdge("lint", "build");
tasks.addEdge("build", "test");
tasks.addEdge("build", "deploy");
tasks.addEdge("test", "deploy");
console.log("order:", tasks.topologicalSort()?.join(", "));
tasks.addEdge("deploy", "install");
console.log("cycle:", tasks.hasCycle());

const roads = new Graph();
roads.addEdge("A", "B", 4);
roads.addEdge("A", "C", 1);
roads.addEdge("C", "B", 2);
roads.addEdge("B", "D", 1);
roads.addEdge("C", "D", 5);
console.log("cheapest from A:", JSON.stringify([...roads.dijkstra("A")]));