Graphs

The 30-second version

Think of a road map. The cities are nodesNode (vertex)One “thing” in a graph: a city, a person, a package, a web page. Vertex is the mathematician's word for the same idea.; the roads between them are edgesEdgeA connection between two nodes: a road, a friendship, an import, a link. An edge can have a direction (an arrow) and a weight (a number).. “What's the fastest way from Hanoi to Hue?” is a question about that map, and it has nothing to do with which country the map shows. The same algorithm works for any map.

That's the trick of this topic: very different problems turn into the same picture.

You've met graphs before even if nobody called them that:

• Social networks: people are nodes, friendships are edges. “People you may know” = friends of your friends.
• Package dependencies: npm install and go build work out what each package needs, and in what order to build them.
• Microservices: service A calls B, B calls C. When C is slow, which user-facing endpoints suffer?
• Build systems and CI pipelines: “test needs build, build needs codegen”. What can run in parallel?
• The web: pages are nodes, links are edges. Search engines rank pages by who links to them.

What you'll be able to do by the end

Everything comes with Go and JavaScript code you can run, and the staff-level part (§11) shows where these algorithms run in real systems: dependency resolvers, deadlock detectors, tracing, search ranking.

Nodes, edges and the words around them

A GraphGraphA set of nodes (vertices) connected by edges — cities and roads, users and friendships, tasks and their dependencies. Edges can have directions and weights. has just two ingredients. A nodeNode (vertex)One “thing” in a graph: a city, a person, a package, a web page. Vertex is the mathematician's word for the same idea. (also called a vertex; plural vertices) is one thing. An edgeEdgeA connection between two nodes: a road, a friendship, an import, a link. An edge can have a direction (an arrow) and a weight (a number). connects two nodes. Everything else is a variation on that. Pick each kind in the widget and click a node:

The vocabulary, in one table

Two more words you'll see in the tables: V is the number of nodes (vertices) and E is the number of edges. A map of 6 towns with 9 roads has V = 6 and E = 9.

Why the three questions matter

Storing a graph in memory

There are three common ways to store the same graph. Think of a school's friendship records:

• Adjacency list — each student has a page in a notebook listing their friends. To find Dee's friends, open Dee's page.
• Adjacency matrix — a huge grid with every student on both axes and a tick where two are friends. Checking “are Ana and Dee friends?” is one glance, but the grid has a square for every pair, even strangers.
• Edge list — a loose pile of cards, one per friendship: “Ana–Ben”, “Ana–Cy”. Easy to write, but finding Dee's friends means flipping through every card.

Toggle between them. Click a node, and change the question:

The trade-offs

(O(…) is Big-O notationBig-O notationA way to describe how an algorithm's cost grows as the input grows, ignoring constant factors: O(1) stays flat, O(n) grows in step with n, O(n²) quadruples when n doubles.: how the cost grows as the graph grows. O(1) means “the same no matter how big”.)

Concrete numbers make the memory row bite. A social network with 1 million users who have ~200 friends each has about 100 million friendships:

• Adjacency list: ~200 million entries (each friendship is stored in both people's lists). At 8 bytes each, roughly 1.6 GB.
• Adjacency matrix: 1,000,000 × 1,000,000 = 10¹² cells. Even at one BitBitThe smallest unit of data: a single 0 or 1. Eight bits make a byte. per cell that's about 125 GB — and 99.98% of those cells are 0.

Real graphs are almost always sparseSparse vs dense graphSparse: each node connects to a few others (road maps, social networks, dependencies) — most real graphs. Dense: most pairs of nodes are connected.: each node connects to a tiny fraction of the others. That's why the adjacency list is the default.

In code

// (inside func main, with import "fmt")
// Adjacency list: node → its neighbours.
g := map[string][]string{
    "A": {"B", "C"},
    "B": {"A", "D"},
    "C": {"A", "D"},
    "D": {"B", "C", "E"},
    "E": {"D"},
}
for _, n := range g["D"] { // neighbours of D: B, C, E
    fmt.Println(n)
}

// Adjacency matrix: nodes numbered 0..4 (A=0, B=1, …).
m := [][]int{
    //  A  B  C  D  E
    {0, 1, 1, 0, 0}, // A
    {1, 0, 0, 1, 0}, // B
    {1, 0, 0, 1, 0}, // C
    {0, 1, 1, 0, 1}, // D
    {0, 0, 0, 1, 0}, // E
}
fmt.Println(m[2][3] == 1) // is there an edge C–D? true

// Edge list: just the pairs.
type Edge struct{ From, To string }
edges := []Edge{{"A", "B"}, {"A", "C"}, {"B", "D"}, {"C", "D"}, {"D", "E"}}
fmt.Println(len(edges)) // 5

Note that this graph is undirected, so every edge is written twice in the list: D appears in B's list and B in D's. For a directed graph you'd store only the arrow's direction.

BFS: ripples in a pond

Drop a stone in a pond. The ripple reaches everything 1 metre away, then 2 metres, then 3. Nothing at 3 metres gets wet before everything at 2 metres has. BFSBFS (breadth-first search)Exploring a graph in rings: first every node 1 edge away, then every node 2 edges away, and so on. Uses a queue. Finds paths with the fewest edges. does the same on a graph — and that's exactly what “degrees of separation” means: your friends are 1 hop away, their friends 2 hops, and so on.

The recipe

BFS needs two helpers:

1. A queueQueue (data structure)A first-in, first-out line: you add at the back and remove from the front, like people waiting at a checkout. — a line at a checkout: new arrivals join at the back, and you always serve the front. It holds nodes we've found but not explored yet (the frontierFrontierThe nodes that have been found but not yet explored — the contents of BFS's queue or DFS's stack. It's the boundary between explored and unexplored territory.).
2. A seen setVisited (seen) setThe set of nodes a traversal has already reached. Checking it before going to a node is what stops an algorithm from looping forever around a cycle. — every node we've already found, so we never add one twice.

Then repeat: take the node at the front, look at its neighbours, and add every new one to the back. Because a node 2 hops away can only be added by a node 1 hop away, everyone at distance 2 lines up behind everyone at distance 1. The queue keeps the rings in order for us.

Step through it on a small friendship graph (neighbours are tried in alphabetical order). Leave the toggle on BFS for now; §05 flips it.

1function bfs(graph, start) {
2  const seen = new Set([start]);
3  const queue = [start];
4  while (queue.length > 0) {
5    const node = queue.shift();  // take from the FRONT
6    visit(node);                 // whatever you need to do with it
7    for (const next of graph.get(node)) {
8      if (!seen.has(next)) {
9        seen.add(next);          // mark when you ADD it
10        queue.push(next);        // join at the BACK
11      }
12    }
13  }
14}

Getting the actual path: parent pointers

BFS as written tells you that H is reachable. (The stepper also tracks each node's distance — the d= labels; in code that's one more map, dist[next] = dist[node] + 1.) To get the route, record a parent pointerParent pointerFor each node, a note of which node you reached it from. Following them backwards from the goal rebuilds the path; then you reverse it. whenever you add a node: “I reached F from D.” At the end, start at the goal and follow parents back to the start — H ← F ← D ← B ← A — then reverse the list. The last step of the stepper above does exactly that.

The same thing on a maze

A grid maze is a graph too: every open cell is a node, and it has an edge to each open cell directly above, right, below and left of it. Run BFS and watch the yellow frontier spread out like a ripple:

On the default maze BFS finds a path of 28 moves after visiting 117 cells. It visits a lot, because it explores every direction evenly — but the path it returns is guaranteed to be the shortest one.

Cost

Every node enters the queue at most once, and every edge is looked at once from each end. So BFS takes O(V + E) time, and O(V) extra memory for the queue and the seen set. That's as fast as you can possibly go: you can't explore a graph without looking at it.

DFS: one corridor at a time

Picture yourself in a maze. You walk down a corridor, and at each fork you take the first unexplored turning. When you hit a dead end, you walk back to the last fork that still has an unexplored turning, and try that. Chalk marks on the walls stop you from exploring a corridor twice. That's DFSDFS (depth-first search)Exploring a graph by following one path as far as it goes, then backing up to the latest fork and trying the next branch. Uses recursion or a stack.: going back is called backtrackingBacktrackingIn DFS: when a node has no unexplored neighbours left, return to the node you came from and try its next neighbour. In recursive code, that's simply the function returning., and the chalk marks are the same seen set BFS used.

Recursion does the remembering

The neatest way to write DFS uses RecursionRecursionA function that solves a problem by calling itself on smaller pieces of it — e.g. a folder's size is the sum of its children's sizes, and a child folder computes its size the same way. It stops at pieces with no children.: to explore a node, mark it, then explore each unseen neighbour by calling the same function. When a call returns, you're automatically back at the node you came from — the Call stackCall stackThe list of functions that are running right now — each one sits on top of the one that called it. When a function returns, its entry (and its local variables) is thrown away. remembers the way back for you.

Flip the toggle below to DFS — it's the same graph as §04 — and step through:

1function dfs(graph, node, seen = new Set()) {
2  seen.add(node);                // discover: first time here
3  for (const next of graph.get(node)) {
4    if (!seen.has(next)) {
5      dfs(graph, next, seen);    // go DEEPER before trying siblings
6    }
7  }
8  // finish: every neighbour explored
9}

Two moments matter for every node, and the stepper tracks both:

• Discovered — the first time DFS arrives (the function is called).
• Finished — when every neighbour has been explored (the function returns).

Here the discovery order is A B D C E F H G, and the first node to finish is G, the deepest one. Finish orderFinish order (DFS)The order in which DFS calls return. A node finishes only after everything reachable from it has finished — which is why reversing it gives a topological order. turns out to be the key to topological sorting (§07).

Compare the shapes. BFS's tree edges fan out in rings, so its path to H has 4 hops. DFS's tree is one long snake, and the path it happened to use to reach H has 6. DFS finds a path, not the shortest path.

On the default maze DFS visits only about 40 cells — far fewer than BFS — because it happened to pick good corridors early. But its path is 38 moves against BFS's 28. Add a few walls and the luck can flip: DFS can also wander through nearly the whole maze before stumbling on the exit. If you need the shortest path, use BFS.

So what is DFS good for?

• “Can I reach X?” and “visit everything” — BFS works too; DFS is often shorter to write.
• Counting connected componentsConnected componentA piece of a graph in which every node can reach every other, with no edges to the rest. A graph split into islands has several components. — run DFS from every node that isn't seen yet; each run colours one component. (“Is our network split in two?”)
• Finding cycles (§06) and ordering dependencies (§07) — this is where DFS really shines, because of its discovered/finished bookkeeping.
• Exploring all possibilities — solving puzzles, generating mazes, trying every move in a game. These are DFS on a graph that's never fully built in memory.

The catch: the call stack has a ceiling

Every recursive call adds a frame to the call stack, and a long path means many nested calls. Here's recursive DFS on a “chain” graph (0 → 1 → 2 → … → 99,999), run on this machine:

const n = 100_000;
const g = Array.from({ length: n }, (_, i) => (i + 1 < n ? [i + 1] : []));
const seen = new Uint8Array(n);
function dfs(u) {
  seen[u] = 1;
  for (const v of g[u]) if (!seen[v]) dfs(v);
}
dfs(0);
// RangeError: Maximum call stack size exceeded
//   (it got 5,707 calls deep on Node 22)

JavaScript gives you a fixed, fairly small stack, so recursive DFS dies at a few thousand levels — very reachable in a real dependency or social graph. Go starts each GoroutineGoroutineA very lightweight task in Go, started with the go keyword. The Go runtime runs thousands of them on just a few OS threads. with a tiny stack and grows it up to 1 GB, so on this machine it lasted 15 million levels and died at 20 million. That's far longer, but a Stack overflowStack overflowThe crash you get when the call stack runs out of room — usually because a recursive function never stops calling itself, or recurses too deeply (tens of thousands of levels in JS). JS throws “RangeError: Maximum call stack size exceeded”; Go prints “fatal error: stack overflow”. in Go is a fatal crash, not a catchable error. Stack & heap §03 shows both in detail.

The fix is to manage the stack yourself: a plain array you push to and pop from, living on the heap where it can grow as large as memory allows.

func DFS(g map[string][]string, start string) []string {
    seen := map[string]bool{}
    var order []string
    stack := []string{start}
    for len(stack) > 0 {
        n := stack[len(stack)-1]     // look at the top
        stack = stack[:len(stack)-1] // pop it
        if seen[n] {
            continue // pushed twice before we got to it
        }
        seen[n] = true
        order = append(order, n)
        nbrs := g[n]
        for i := len(nbrs) - 1; i >= 0; i-- { // push in reverse…
            if !seen[nbrs[i]] {
                stack = append(stack, nbrs[i]) // …so the first neighbour is popped first
            }
        }
    }
    return order
}

On the friendship graph both print A B D C E F H G — the same discovery order as the recursive version. Pick “DFS (explicit stack)” in the stepper above to watch it run, including a node that gets pushed twice and skipped.

Finding cycles: white, grey, black

Cycles are usually bad news in software. Package A imports B, B imports C, C imports A: which one gets built first? None can. Go refuses to compile it, and it tells you the exact loop:

$ go build .
package example.com/app
	imports example.com/app/a from main.go
	imports example.com/app/b from a.go
	imports example.com/app/a from b.go: import cycle not allowed

That's an Import cycleImport cyclePackage A imports package B and B imports A (possibly via others). Go refuses to compile it: “import cycle not allowed”., and go build found it — while loading packages, before compiling anything — with the algorithm in this section.

Why “seen / not seen” isn't enough

Your first idea might be: run DFS, and if you ever reach a node you've seen before, there's a cycle. Try it on this shape:

app → log  → fmt
app → auth → fmt

DFS goes app → log → fmt, then app → auth → fmt. fmt was seen already, but there's no cycle — two packages simply share a dependency (a diamondDiamond dependencyTwo packages that both depend on the same third package (A → B → D and A → C → D). It's a shared dependency, not a cycle.). We need to tell apart “seen, and still in progress” from “seen, and completely finished”. Hence three colours:

The rule: an edge to a GREY node is a back edgeBack edgeDuring DFS, an edge that points to a node still on the current path (a “grey” node). In a directed graph, finding one proves there is a cycle., and a back edge means a cycle. The grey node is still waiting for the current chain of calls to finish — and that chain just led back to it. An edge to a BLACK node is harmless: that node, and everything after it, was already fully explored without finding a way back.

1function visit(n) {
2  color[n] = GREY;               // on the current path
3  for (const d of imports[n]) {
4    if (color[d] === GREY) {
5      throw cycle(d);            // back edge: d is still open!
6    }
7    if (color[d] === WHITE) visit(d);
8    // BLACK: finished earlier and known safe → skip
9  }
10  color[n] = BLACK;              // done: no cycle through n
11}

When the back edge config → auth shows up, the cycle is sitting right there on the call stack: start at auth and read to the top — auth → db → config → auth. That's how compilers and package managers print the loop for you instead of just saying “cycle somewhere”.

Undirected graphs are simpler (with one twist)

In an undirected graph, every edge works both ways, so the moment DFS goes A → B, B can see A as a neighbour. That's not a cycle — it's the edge you just walked along. The rule becomes: a seen neighbour that isn't the node you came from means a cycle. Two colours (seen / not seen) are enough, as long as you remember each node's parent.

An even simpler way for undirected graphs is union-find (§09): add edges one at a time, and if an edge joins two nodes that are already connected, that edge closes a loop.

Topological sort: a valid order for dependencies

Getting dressed: socks before shoes, trousers before shoes, shirt before tie. There are many valid orders (shirt first or socks first — both fine) and some invalid ones (shoes before socks). A Topological sortTopological sortPutting the nodes of a DAG in a line so every edge points forward: each task comes after everything it depends on. Only possible when there's no cycle. picks one valid order. Your build tool, your package manager and your CI system do this every time they run.

Kahn's algorithm: “who's waiting for nothing?”

Draw an arrow from each task to the tasks that need it: install → lint means “install must finish before lint”. A task's In-degreeIn-degreeHow many edges point into a node. In a dependency graph: how many things this task still waits for. is the number of arrows pointing at it — how many things it's still waiting for.

needs["test"] = ["build"]

after["build"] = ["test"]

Kahn's algorithmKahn's algorithmA topological sort: repeatedly take a node that depends on nothing still unfinished (in-degree 0), output it, and remove its outgoing edges. Left-over nodes mean a cycle. is how a sensible person would schedule work:

1. Find every task that waits for nothing (in-degree 0). Those can start now.
2. Take one, do it, and cross out its outgoing arrows. Each task it pointed to now waits for one thing fewer.
3. Any task whose count drops to 0 has become ready. Add it to the ready list.
4. Repeat until the ready list is empty.

If every task got done, the order you did them in is a valid order. If some tasks are left over, there's a cycle: each leftover task is either on a cycle, or waits (directly or indirectly) for a task that is.

Play with it. The starting graph is a small CI pipeline. Then add deploy must finish before install and watch it fail:

Two things to notice:

• Waves = parallelism. Every task in the same column became ready at the same moment, so with enough workers they can run together. codegen and lint both only need install. The number of waves is the shortest possible total time if every task takes one unit — the length of the longest dependency chain, the critical pathCritical pathThe longest chain of steps that must happen one after another. It sets the minimum total time; speeding up anything not on it changes nothing..
• A cycle stops the algorithm early, and it tells you who's stuck. The good error message then names the actual loop, using the three-colour DFS from §06 on the stuck tasks. “Cycle detected” alone is a terrible error; install → codegen → build → test → package → deploy → install is a useful one.

The code

Here's the CI pipeline as data, and Kahn's algorithm in both languages:

// Kahn returns tasks in a valid order. after[n] lists what must come after n.
func Kahn(after map[string][]string, nodes []string) ([]string, error) {
    indeg := map[string]int{}
    for _, n := range nodes {
        for _, m := range after[n] {
            indeg[m]++ // m waits for one more thing
        }
    }
    var ready []string
    for _, n := range nodes {
        if indeg[n] == 0 {
            ready = append(ready, n)
        }
    }
    var order []string
    for len(ready) > 0 {
        n := ready[0]
        ready = ready[1:]
        order = append(order, n)
        for _, m := range after[n] {
            indeg[m]--
            if indeg[m] == 0 { // the last thing m waited for is done
                ready = append(ready, m)
            }
        }
    }
    if len(order) < len(nodes) {
        return nil, errors.New("cycle!")
    }
    return order, nil
}

// In main:
nodes := []string{"checkout", "install", "codegen", "lint", "build", "test", "package", "deploy"}
after := map[string][]string{
    "checkout": {"install"},
    "install":  {"codegen", "lint"},
    "codegen":  {"build"},
    "build":    {"test"},
    "lint":     {"package"},
    "test":     {"package"},
    "package":  {"deploy"},
}
fmt.Println(Kahn(after, nodes))
// [checkout install codegen lint build test package deploy] <nil>

Why does the Go version take a separate nodes list? Two reasons. A task with no arrows at all (and deploy, which has no key in after) would otherwise never be seen. And Go randomises map iteration order, so looping over after would give a different, still valid, order on every run; a slice keeps it stable. The JS version collects every task it meets into the indeg Map instead, and a JS Map remembers insertion order.

§10 has the production version, which also reports which cycle.

The DFS way: reverse finish order

There's a second classic algorithm, and it falls straight out of §05. In DFS, a node finishes only after everything reachable from it has finished. So if every arrow points from “first” to “after”, each node finishes after all the things that must come after it. Reverse the finish order, and every task comes before what follows it:

function topoDFS(after) {
  const seen = new Set();
  const finished = [];
  const visit = (n) => {
    seen.add(n);
    for (const m of after.get(n) ?? []) if (!seen.has(m)) visit(m);
    finished.push(n); // n finishes only after everything that comes after it
  };
  for (const n of after.keys()) if (!seen.has(n)) visit(n);
  return finished.reverse();
}
// checkout → install → lint → codegen → build → test → package → deploy

Different from Kahn's output (lint before codegen), and equally valid. This short version doesn't notice cycles — add the three colours from §06 and fail on a grey neighbour to make it safe. It also uses recursion, so §05's stack-depth warning applies.

Dijkstra: cheapest paths with weights

BFS counts hops, which is wrong as soon as edges cost different amounts: a 3-road route of 2 minutes each beats a 1-road route of 40 minutes. On a weighted graphWeighted graphA graph where each edge carries a number — distance, time, cost, latency. A shortest path is then the one with the smallest total weight, not the fewest edges. we need Dijkstra's algorithmDijkstra's algorithmFinds the cheapest path from one start node to every other node when edge weights are zero or positive. It always expands the closest unfinished node next, using a priority queue..

The idea, with towns

You're in town A. Every other town starts as “∞ — no route known”. Now repeat:

1. Among towns you haven't finished, pick the one with the smallest known distance. Call it u.
2. Mark u as finished: its distance is final.
3. For each road u → v of length w: if going through u is cheaper than the best route to v known so far (dist[u] + w < dist[v]), update dist[v]. This is called relaxing the edgeRelaxing an edgeChecking whether going through the current node gives a cheaper route to a neighbour: if dist[u] + w < dist[v], update dist[v] (and remember u as v's parent)..

Why is step 2 safe? Say u is the closest unfinished town, at distance 8. Any other route to u would have to leave the finished area through some unfinished town — and all of those are already at least 8 away. Since road lengths are never negative, the detour can only add to that. So nothing can ever beat 8. That argument is the whole algorithm, and it's also exactly what breaks with negative weights (below).

Finding “the smallest” fast: a priority queue

Step 1 asks for the minimum over all unfinished towns, again and again. Scanning every town each time costs O(V) per step. A Priority queuePriority queueA queue that hands out the most important item first instead of the oldest. Usually built on a heap, so adding and removing are fast even with many items. does it in O(log V): it hands out the item with the smallest key first — like an emergency room calling the most urgent patient, not whoever arrived first. It's usually built on a binary heap; the Heaps topic shows how one works inside. Here we just use it: push(dist, town) and pop() → the smallest.

Step through it. The numbers above the towns are the best distances known so far; the heap is shown sorted for readability:

1dist.set(src, 0);
2heap.push([0, src]);
3while (heap.size > 0) {
4  const [d, node] = heap.pop();      // closest unfinished
5  if (done.has(node)) continue;      // stale entry → skip
6  done.add(node);
7  for (const [to, w] of graph.get(node)) {
8    const nd = d + w;
9    if (!dist.has(to) || nd < dist.get(to)) {
10      dist.set(to, nd);              // found a cheaper way
11      prev.set(to, node);
12      heap.push([nd, to]);
13    }
14  }
15}

Two things the stepper shows that textbooks often skip:

• Distances improve. B starts at 4 (the direct road) and drops to 3 when we find A → C → B. E starts at 12, then drops to 10.

• Stale entries. When B improved to 3, its old entry (4, B) was still in the queue. There are two ways to deal with that:

  • Update it in place (“decrease-key”). Go's container/heap can do this with heap.Fix, but only if every item remembers its current position in the heap array, which you have to keep up to date on every swap — Heaps §07 shows how. JavaScript has no built-in heap at all.
  • Leave it and push a fresh copy. Push (3, B) as well, and when the old (4, B) is eventually popped, skip it, because B is already finished. This is Lazy deletionLazy deletion (stale entries)Instead of updating an item already inside a priority queue, push a new, better copy and skip the old one when it's eventually popped. Simpler code, slightly bigger queue.. The queue holds a few extra entries (at most one per edge), but the code stays short and no position tracking is needed.

  We use lazy deletion here, and it's the more common choice in practice. Both give the same answers and the same O-cost.

The code

import "container/heap"

type Edge struct {
    To     string
    Weight int // must be >= 0 for Dijkstra
}

// item is one entry in the priority queue: "we can reach node at cost dist".
type item struct {
    node string
    dist int
}

// pq implements heap.Interface: a min-heap ordered by dist.
type pq []item

func (h pq) Len() int           { return len(h) }
func (h pq) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h pq) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *pq) Push(x any)        { *h = append(*h, x.(item)) }
func (h *pq) Pop() any {
    old := *h
    x := old[len(old)-1]
    *h = old[:len(old)-1]
    return x
}

func Dijkstra(g map[string][]Edge, src string) (dist map[string]int, prev map[string]string) {
    dist = map[string]int{src: 0}
    prev = map[string]string{}
    done := map[string]bool{}
    h := &pq{{src, 0}}
    for h.Len() > 0 {
        cur := heap.Pop(h).(item) // the closest node we haven't finished
        if done[cur.node] {
            continue // stale entry: we already found a shorter way here
        }
        done[cur.node] = true
        for _, e := range g[cur.node] {
            nd := cur.dist + e.Weight
            if old, ok := dist[e.To]; !ok || nd < old { // relax the edge
                dist[e.To] = nd
                prev[e.To] = cur.node
                heap.Push(h, item{e.To, nd}) // the old entry stays; skipped later
            }
        }
    }
    return dist, prev
}

Run on the map above, from A, both report F = 12 via A C B D E F (§10 has the tests).

Cost

Every edge can push one entry, and every push and pop costs O(log E). Total: O((V + E) log V) (log E and log V differ by at most a factor of 2, since E ≤ V²). For a road network with a million junctions, that's tens of millions of cheap steps — well under a second.

Negative weights break it — Bellman-Ford instead

Dijkstra's safety argument was “detours can only add”. A negative edge (a road that pays you to use it — in real systems: a cashback or a time credit) breaks that: a route through a far-away node can come back cheaper, after the node it improves was already finished. Q5 in the quiz (§13) walks through exactly how the result goes wrong.

Bellman-FordBellman-FordA shortest-path algorithm that works with negative edge weights: it relaxes every edge V − 1 times. Slower than Dijkstra (O(V·E)), and it can detect negative cycles. handles negative edges by brute patience: relax every edge, and repeat V − 1 times. A cheapest path uses at most V − 1 edges, and each round fixes at least one more of them. It's O(V·E) — much slower — but it has a bonus: if a V-th round still improves something, there's a Negative cycleNegative cycleA cycle whose weights add up to less than zero. Going round it again always makes the path cheaper, so “shortest path” has no answer. and no shortest path exists at all. Some network routing protocols, like RIP (an old protocol routers use to share routes with their neighbours), use this family of algorithms because it works with each router knowing only its neighbours.

A*: Dijkstra with a sense of direction

Dijkstra spreads out in every direction equally, like BFS's ripple but weighted. If you're driving from Hanoi to Hue, it will happily explore roads going north first. A* searchA* searchDijkstra plus a guess of the remaining distance to the goal (a heuristic, like straight-line distance on a map). It explores toward the goal first, so it usually visits far fewer nodes. adds a HeuristicHeuristicA quick, educated guess used to guide a search — e.g. “as the crow flies” distance to the destination. For A* to stay correct it must never overestimate.: an estimate of the remaining distance, like the straight-line distance to Hue. It orders the priority queue by distance so far + estimated distance left, so roads pointing toward the goal get explored first. As long as the estimate never overestimates (a straight line is never longer than the real road) — and, if you never revisit finished nodes as our code does, it also never drops by more than the length of the road you just took (it's consistent) — A* still finds the cheapest route, usually after visiting a small fraction of the nodes. Straight-line distance satisfies both conditions. Map apps and game pathfinding use A* and its relatives.

Union-find and minimum spanning trees

Imagine you're laying fibre cable between towns. Every possible link has a cost, and you want every town connected to every other (directly or through others) for the least total cable. You don't care about the route between any particular pair — just that the network is in one piece. That's a minimum spanning treeMinimum spanning tree (MST)The cheapest set of edges that still connects every node, with no cycles. Think: the least cable needed to connect every town. A spanning tree on V nodes always has exactly V − 1 edges. (MST): the cheapest set of edges that connects all nodes, with no loops (a loop would mean one cable is redundant).

Kruskal's algorithm: cheapest first, skip loops

Kruskal's algorithmKruskal's algorithmBuilds a minimum spanning tree by sorting all edges by weight and taking them cheapest-first, skipping any edge that would connect two already-connected nodes. is almost embarrassingly simple:

1. Sort all edges from cheapest to most expensive.
2. Go through them in order. Take an edge unless its two towns are already connected — then it would only close a loop.
3. Stop when you've taken V − 1 edges (that's exactly how many a tree on V nodes has).

Step 2 needs to answer “are A and B already connected?” over and over, while the answer keeps changing as edges are added. Running BFS each time would cost O(V + E) per edge. That's what union-find is for.

Union-find in one picture

Union-findUnion-find (disjoint sets)A data structure that tracks which items are in the same group. find(x) returns the group's representative; union(a, b) merges two groups. Both are almost O(1). keeps every item in a group, and each group has one representative (its root). Think of clubs, where each club has a president:

• find(x) — “who is x's president?” Follow x's parent pointer, then that node's parent, and so on, until you reach a node that is its own parent: the root.
• union(a, b) — merge two clubs: make one president report to the other.

Two items are connected exactly when find(a) == find(b). Step through Kruskal on the same map as Dijkstra:

type UnionFind struct {
    parent, size []int
}

func NewUnionFind(n int) *UnionFind {
    u := &UnionFind{parent: make([]int, n), size: make([]int, n)}
    for i := range n { // Go 1.22+: range over an int counts 0..n-1
        u.parent[i] = i // everyone starts as their own root
        u.size[i] = 1
    }
    return u
}

func (u *UnionFind) Find(x int) int {
    for u.parent[x] != x {
        u.parent[x] = u.parent[u.parent[x]] // path halving: skip a level as we climb
        x = u.parent[x]
    }
    return x
}

// Union merges the groups of a and b. It reports false if they were already together.
func (u *UnionFind) Union(a, b int) bool {
    ra, rb := u.Find(a), u.Find(b)
    if ra == rb {
        return false
    }
    if u.size[ra] < u.size[rb] {
        ra, rb = rb, ra // attach the smaller tree under the bigger one
    }
    u.parent[rb] = ra
    u.size[ra] += u.size[rb]
    return true
}

Kruskal, for real

UnionFind works on numbers 0…n−1, but our towns have names. So step one is to give each town a number; then sort the roads and keep each one that Union accepts:

type Road struct {
    A, B string
    Cost int
}

// Kruskal returns the roads of a minimum spanning tree and their total cost.
func Kruskal(towns []string, roads []Road) ([]Road, int) {
    idx := map[string]int{} // UnionFind works on 0..n-1, so number the towns
    for i, t := range towns {
        idx[t] = i
    }
    sorted := slices.Clone(roads) // don't reorder the caller's slice
    slices.SortStableFunc(sorted, func(x, y Road) int { return cmp.Compare(x.Cost, y.Cost) })

    uf := NewUnionFind(len(towns))
    var tree []Road
    total := 0
    for _, r := range sorted {
        if uf.Union(idx[r.A], idx[r.B]) { // false = already connected → skip
            tree = append(tree, r)
            total += r.Cost
            if len(tree) == len(towns)-1 {
                break // a tree on V nodes has exactly V-1 edges
            }
        }
    }
    return tree, total
}

// In main:
towns := []string{"A", "B", "C", "D", "E", "F"}
roads := []Road{
    {"A", "B", 4}, {"A", "C", 2}, {"B", "C", 1}, {"B", "D", 5}, {"C", "D", 8},
    {"C", "E", 10}, {"D", "E", 2}, {"D", "F", 6}, {"E", "F", 2},
}
fmt.Println(Kruskal(towns, roads))
// [{B C 1} {A C 2} {D E 2} {E F 2} {B D 5}] 12

Same five roads as the stepper, total 12.

Why it's “almost O(1)”

Two small tricks keep the parent chains extremely short:

• Union by size — always hang the smaller tree under the bigger one. A node's depth only grows when its group at least doubles, so no chain gets longer than log₂ V.
• Path compressionPath compressionA union-find speed-up: while find(x) walks up to the root, it re-points every node it passed directly at the root, so the next find is one hop. — while find climbs to the root, re-point the nodes it passes closer to the root, so the next find is shorter. The code above uses the simplest version, path halving: each node it passes skips one level.

With both tricks, a sequence of operations costs so little that the per-operation cost grows slower than log of log of anything you'll ever store. For practical purposes, constant time.

Where union-find shows up

• Connectivity while edges arrive: “are these two servers in the same network partition?”, “are these two pixels part of the same blob?”
• Grouping duplicates: if record A matches B and B matches C, union them all; each final group is one real-world customer.
• Cycle detection in undirected graphs: an edge whose two ends are already in the same group closes a cycle (§06).

What it can't do: split groups again. Union-find only merges, so it doesn't fit graphs where edges get deleted.

The real code, with tests

Everything below was run on this machine with Go 1.24 and Node 22. The Go package has four files: bfs.go, topo.go, dijkstra.go (exactly the code in §08) and a test file. The JS module mirrors it.

1. BFS shortest path

// ShortestPath returns the fewest-hops path from start to goal, or nil if
// goal can't be reached. g maps each node to its neighbours.
func ShortestPath[N comparable](g map[N][]N, start, goal N) []N {
    parent := map[N]N{start: start} // doubles as the visited set
    queue := []N{start}
    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:] // dequeue from the front
        if cur == goal {
            // Walk the parent pointers back to start, then reverse.
            path := []N{cur}
            for cur != start {
                cur = parent[cur]
                path = append(path, cur)
            }
            for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
                path[i], path[j] = path[j], path[i]
            }
            return path
        }
        for _, next := range g[cur] {
            if _, seen := parent[next]; !seen { // mark when ENQUEUED, not when dequeued
                parent[next] = cur
                queue = append(queue, next)
            }
        }
    }
    return nil
}

The JS version uses a head index instead of queue.shift(). shift() has to move every remaining element one slot to the left, so it costs O(length of the queue). With a small queue that's invisible, but BFS on a big graph can have a huge frontier. Measured on this machine (Node 22), BFS over a social graph with 200,000 people and ~10 friends each, where the queue peaked at 123,935 entries:

The Go version's queue = queue[1:] is O(1): it just moves the start of the slice forward, no copying.

2. Topological sort that names the cycle

This version takes the graph the way package managers and build files describe it: each task lists what it needs (needs["test"] = ["build"]). That's the §06 direction (arrows point at what you need), the opposite of §07's after — so the code first builds the reverse map, users, which is exactly §07's after. It runs Kahn's algorithm (§07), and if tasks are left over, runs the three-colour DFS from §06 on them to find a cycle to report.

import (
    "maps"
    "slices"
    "strings"
)

// CycleError reports one cycle that makes an ordering impossible.
type CycleError struct{ Cycle []string }

func (e *CycleError) Error() string {
    return "dependency cycle: " + strings.Join(e.Cycle, " → ")
}

// TopoSort orders tasks so every task comes after everything it needs.
// needs["test"] = ["build"] means build must run before test.
func TopoSort(needs map[string][]string) ([]string, error) {
    // 1. Collect every node and count, for each one, how many things it still waits for.
    indeg := map[string]int{}
    users := map[string][]string{} // reverse edges: dep → tasks that need it
    for task, deps := range needs {
        if _, ok := indeg[task]; !ok {
            indeg[task] = 0
        }
        for _, d := range deps {
            if _, ok := indeg[d]; !ok {
                indeg[d] = 0
            }
            indeg[task]++
            users[d] = append(users[d], task)
        }
    }
    // 2. Start with every task that waits for nothing. Sorted, so output is stable
    //    (Go randomises map iteration order).
    var ready []string
    for _, n := range slices.Sorted(maps.Keys(indeg)) {
        if indeg[n] == 0 {
            ready = append(ready, n)
        }
    }
    // 3. Kahn's loop: take a ready task, "finish" it, unlock whoever waited on it.
    var order []string
    for len(ready) > 0 {
        n := ready[0]
        ready = ready[1:]
        order = append(order, n)
        next := users[n]
        slices.Sort(next)
        for _, u := range next {
            indeg[u]--
            if indeg[u] == 0 {
                ready = append(ready, u)
            }
        }
    }
    if len(order) == len(indeg) {
        return order, nil
    }
    // 4. Some tasks never became ready: they sit on (or behind) a cycle. Find one.
    return nil, &CycleError{Cycle: findCycle(needs, indeg)}
}

// findCycle runs DFS over the leftover tasks (indeg > 0) with three colours.
func findCycle(needs map[string][]string, indeg map[string]int) []string {
    const (
        white = iota // not visited yet
        grey         // on the current DFS path
        black        // finished, known cycle-free
    )
    color := map[string]int{}
    var path []string
    var cycle []string
    var visit func(n string) bool
    visit = func(n string) bool {
        color[n] = grey
        path = append(path, n)
        for _, d := range needs[n] {
            switch color[d] {
            case grey: // back edge: d is already on the path → cycle
                i := slices.Index(path, d)
                cycle = append(slices.Clone(path[i:]), d)
                return true
            case white:
                if visit(d) {
                    return true
                }
            }
        }
        path = path[:len(path)-1]
        color[n] = black
        return false
    }
    for _, n := range slices.Sorted(maps.Keys(indeg)) {
        if indeg[n] > 0 && color[n] == white && visit(n) {
            break
        }
    }
    return cycle
}

3. Dijkstra

The Go side is exactly the Dijkstra function from §08. JavaScript has no built-in priority queue, so graph.js defines a tiny binary min-heap above dijkstra (the function from §08). How it works is the subject of Heaps:

// A tiny binary min-heap of [dist, node] pairs (see the Heaps topic for how it works).
class MinHeap {
  #a = [];
  get size() { return this.#a.length; }
  push(x) {
    const a = this.#a;
    a.push(x);
    for (let i = a.length - 1; i > 0; ) {
      const p = (i - 1) >> 1;
      if (a[p][0] <= a[i][0]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.#a;
    const top = a[0];
    const last = a.pop();
    if (a.length) {
      a[0] = last;
      for (let i = 0; ; ) {
        const l = 2 * i + 1, r = l + 1;
        let m = i;
        if (l < a.length && a[l][0] < a[m][0]) m = l;
        if (r < a.length && a[r][0] < a[m][0]) m = r;
        if (m === i) break;
        [a[m], a[i]] = [a[i], a[m]];
        i = m;
      }
    }
    return top;
  }
}

The tests

package graph

import (
    "errors"
    "fmt"
    "slices"
    "testing"
)

var friends = map[string][]string{
    "A": {"B", "C"}, "B": {"A", "D"}, "C": {"A", "D", "E"},
    "D": {"B", "C", "F"}, "E": {"C", "F", "G"}, "F": {"D", "E", "H"},
    "G": {"E", "H"}, "H": {"F", "G"},
}

func TestShortestPath(t *testing.T) {
    tests := []struct {
        from, to string
        want     []string
    }{
        {"A", "A", []string{"A"}},
        {"A", "H", []string{"A", "B", "D", "F", "H"}},
        {"A", "Z", nil}, // unreachable
    }
    for _, tc := range tests {
        got := ShortestPath(friends, tc.from, tc.to)
        if !slices.Equal(got, tc.want) {
            t.Errorf("ShortestPath(%s→%s) = %v, want %v", tc.from, tc.to, got, tc.want)
        }
    }
}

func TestTopoSortCycle(t *testing.T) {
    needs := map[string][]string{"a": {"b"}, "b": {"c"}, "c": {"a"}, "d": {"a"}}
    _, err := TopoSort(needs)
    var ce *CycleError
    if !errors.As(err, &ce) {
        t.Fatalf("want *CycleError, got %v", err)
    }
    if len(ce.Cycle) != 4 || ce.Cycle[0] != ce.Cycle[3] {
        t.Errorf("bad cycle %v", ce.Cycle)
    }
}

func ExampleTopoSort() {
    order, err := TopoSort(map[string][]string{
        "test": {"build"}, "build": {"install"}, "lint": {"install"},
        "deploy": {"test", "lint"},
    })
    fmt.Println(order, err)

    _, err = TopoSort(map[string][]string{
        "auth": {"db"}, "db": {"config"}, "config": {"auth"}, "app": {"auth"},
    })
    fmt.Println(err)
    // Output:
    // [install build lint test deploy] <nil>
    // dependency cycle: auth → db → config → auth
}

$ go test -v .
=== RUN   TestShortestPath
--- PASS: TestShortestPath (0.00s)
=== RUN   TestTopoSortOrder
--- PASS: TestTopoSortOrder (0.00s)
=== RUN   TestTopoSortCycle
--- PASS: TestTopoSortCycle (0.00s)
=== RUN   TestDijkstra
--- PASS: TestDijkstra (0.00s)
=== RUN   ExampleTopoSort
--- PASS: ExampleTopoSort (0.00s)
=== RUN   ExampleDijkstra
--- PASS: ExampleDijkstra (0.00s)
PASS
ok      example.com/graph       0.003s

$ node --test --test-reporter=spec
✔ BFS finds the fewest hops (0.9ms)
✔ topoSort puts dependencies first (0.3ms)
✔ topoSort reports the cycle (0.4ms)
✔ dijkstra (0.6ms)
ℹ tests 4
ℹ pass 4
ℹ fail 0

(The full Go test file also has TestTopoSortOrder, which checks every dependency comes before its task, plus TestDijkstra and ExampleDijkstra on the road map from §08 — 12 [A C B D E F].)

Complexity at a glance

V = number of nodes, E = number of edges. See Big-O if the notation is new.

Graphs inside real systems

Dependency resolution: same graph, two philosophies

Every package manager walks a dependency graph: your project needs packages, which need packages, and so on. The hard part isn't the walk (that's BFS or DFS). It's choosing which version of each package to use when different packages ask for different ones.

Go modules: minimal version selectionMinimal version selection (MVS)Go's way of choosing dependency versions: walk the module graph and, for each module, take the highest of the minimum versions anyone asked for — never newer. Simple and reproducible, no solver.. Each go.mod states the minimum version it needs of each dependency (a Go moduleGo moduleA versioned set of Go packages defined by a go.mod file — roughly what an npm package is in JavaScript. Other projects import your module by its path, e.g. github.com/you/app. requirement like require example.com/a v1.2.0 means “1.2.0 or newer”). Go walks the whole requirement graph and, for each module, picks the highest of the minimums anyone asked for — never anything newer than that. A worked example:

Go selects A v1.3.0 — the max of 1.2.0 and 1.3.0 — even if A v1.9.0 exists. It's one graph walk, no search, and the same inputs always give the same answer, which is why Go doesn't need a lockfile to be reproducible (go.sum stores checksums, not choices). You can print the graph yourself with go mod graph, one edge per line.

npm: newest matching, with duplicates allowed. npm requirements are Semantic versioningSemantic versioning (semver)Version numbers shaped MAJOR.MINOR.PATCH, like 1.4.2. Bump MAJOR for breaking changes, MINOR for new features, PATCH for fixes. Ranges like ^1.4.0 mean “1.4.0 or any newer 1.x”. ranges like ^1.2.0 (“any 1.x from 1.2.0 up”), and npm picks the newest version that fits. When two packages need incompatible versions of the same library, npm can install both, nesting one copy under the package that needs it in node_modules. The result depends on what was published today, so package-lock.json records the exact choices to make installs repeatable.

Deadlock detection: look for a cycle

A DeadlockDeadlockTwo or more tasks each wait for something another one holds, so none can ever continue — e.g. transaction A waits for B's row lock while B waits for A's. Go crashes with “all goroutines are asleep” when every goroutine is stuck; databases detect it and abort one transaction. is a cycle in a Wait-for graphWait-for graphA drawing of who waits for whom: an arrow from each waiting task to whatever it's waiting for. A deadlock is a loop (a cycle) in this graph.: draw an arrow from each waiting task to the task holding what it needs. T1 waits for T2's lock, T2 waits for T3's, T3 waits for T1's — a cycle, so nobody can ever continue.

Databases look for exactly that. PostgreSQL, for example, lets a blocked transaction wait for deadlock_timeout (1 second by default), then builds the wait-for graph among the waiting transactions and searches it for a cycle. If it finds one, it aborts one of the transactions on it with ERROR: deadlock detected, which breaks the cycle and lets the others continue. The full story is in Race conditions §10.

One subtlety: Go's fatal error: all goroutines are asleep - deadlock! is not cycle detection. The runtime just notices that no goroutine can run at all. Two goroutines deadlocked on each other while a third keeps running (say, an HTTP server) won't trigger it — that's why production hangs need the debugging tools from Race conditions §11.

Call graphs, tracing and blast radius

Services calling services form a directed Call graphCall graphA graph of which functions (or services) call which. Static call graphs come from reading the code; dynamic ones come from recording real calls, e.g. traces.. You rarely draw it by hand: distributed tracing records every request as a tree of spansTracing / spanDistributed tracing records the path of one request through your code and services. Each timed step (one middleware, one DB query) is a span, so you can see where the time went., and tracing tools merge millions of those trees into a service map — a graph of who calls whom, with request rates and latencies as edge weights.

Once you have that graph, everyday questions become graph walks. Try the first two here:

• “If auth goes down, what breaks?” — BFS over the arrows backwards from auth: everything that calls it, directly or indirectly. This is your blast radius, and it's how you decide what to fail gracefully.
• “What does checkout need to be up?” — BFS forwards. If the answer is “nearly everything”, checkout's availability is roughly the product of all their availabilities.
• “Why is this request slow?” — inside one trace, the spans form a tree (each span's parent is the call that started it). The critical pathCritical pathThe longest chain of steps that must happen one after another. It sets the minimum total time; speeding up anything not on it changes nothing. is the longest chain of spans that ran one after another; speeding up anything off that path doesn't make the request faster.

PageRank: importance flowing along edges

Early search engines ranked pages by their words, which was easy to game. PageRankPageRankGoogle's original idea for ranking web pages: a page is important if important pages link to it. Computed by repeatedly passing “importance” along the links until the numbers settle. ranked them by the link graph instead: a page is important if important pages link to it. Picture a random surfer who keeps clicking random links (and now and then jumps to a random page). PageRank is the fraction of time they'd spend on each page. You compute it by starting every page with equal score and repeatedly passing each page's score out along its links, split evenly, until the numbers stop changing — a few dozen rounds over the whole graph. The same idea ranks influential accounts, important packages in an ecosystem, and suspicious accounts in fraud rings.

Graph queries in a database

When the graph lives in a relational database, SQL's WITH RECURSIVE can walk it. Here's “degrees of separation” on the friendship graph from §04, run on PostgreSQL 16:

WITH RECURSIVE reach(node, hops) AS (
    SELECT 'A', 0                          -- start
  UNION                                    -- UNION (not UNION ALL) drops exact duplicates
    SELECT e.dst, r.hops + 1
    FROM reach r JOIN edge e ON e.src = r.node
    WHERE r.hops < 4                       -- stop after 4 hops, or it never ends
)
SELECT node, min(hops) AS degrees
FROM reach GROUP BY node ORDER BY degrees, node;
--  A 0 · B 1 · C 1 · D 2 · E 2 · F 3 · G 3 · H 4

(edge is a view that lists each friendship in both directions.) It's BFS level by level, with one important difference: there's no global visited set. UNION only removes identical (node, hops) rows, so a node reached at hop 2 is explored again at hop 3 and 4. Here the 8 people produced 14 rows; on a real social graph that blows up fast, which is why the hop limit is mandatory. When multi-hop traversals are the core of the product, a graph database (Graph databaseGraph databaseA database (Neo4j, Amazon Neptune) that stores nodes (things) and relationships (links between things) directly, so following links many hops deep is cheap.) stores each node's neighbours as direct pointers and runs these walks natively.

When the graph doesn't fit in memory

A web crawl or a large social network has billions of nodes and hundreds of billions of edges — terabytes, far beyond one machine's RAM. The playbook:

• Compress first. Replace string IDs with integers 0…V−1 and store neighbours in CSR form (two flat arrays, §03). Plenty of “big” graphs fit on one large machine after that, and a single machine avoids all network costs.
• Partition. Split the nodes across machines. The catch: every edge that crosses machines turns one array read into a network message, and real graphs have no clean cuts — a few “celebrity” nodes connect to everything. Partitioners try to keep neighbours together, often by splitting celebrity nodes' edges across machines instead.
• Think like a vertex. Systems in the Pregel family (Google's Pregel, Apache Giraph, Spark GraphX) run algorithms in rounds: every node reads the messages its neighbours sent last round, updates itself, and sends new messages. BFS becomes “if I just got reached, tell my neighbours”; PageRank becomes “send my score / out-degree to each neighbour”. Each round is one big parallel step with a barrier at the end.
• Precompute. Production systems rarely run BFS over a billion-node graph per request. They precompute (friends-of-friends lists, PageRank scores, reachability indexes) in batch jobs and serve the results from a cache or key-value store.

Pitfalls gallery

Check yourself

Predict before you click. Q1–Q2 are covered in §04–§05, Q3 in §04 and §12, Q4 in §07, Q5 in §08 and §10, Q6 in §09.

const graph = new Map([
  ["A", ["B", "C"]], ["B", ["D"]], ["C", ["D"]], ["D", []],
]);
// BFS from A, neighbours in listed order, mark on enqueue
console.log(bfsOrder(graph, "A").join(" "));

queue := []string{start}
for len(queue) > 0 {
    cur := queue[0]
    queue = queue[1:]
    for _, next := range g[cur] {
        queue = append(queue, next) // no seen check
    }
}

Cheat sheet