Minimum Spanning Trees: Kruskal and Prim

in reviewThis lesson is complete and being validated before release - details may still change.

Minimum spanning trees

Loading interactive demo…

Waypoints joined by weighted edges, the weights their lengths. The tree keeps the fewest edges that connect every waypoint, for the least total weight. Kruskal walks every edge cheapest first and keeps each one whose ends a union-find says are still apart; Prim grows one tree from the start node, its frontier edges waiting on a heap, and drops an entry whose node joined meanwhile.Take the tour, or press and explore. Legend:

The panel beside the stage is the real MinimumSpanningTree class from the published library executing in your browser, with the current line highlighted.

Edges accepted into the tree, and the nodes they have reached.
Prim's frontier: nodes a heap entry can reach, hollow.
Edges not yet considered, and dashed the ones rejected or found stale.
The edge being considered, pushed, or accepted.

The upper strip is Kruskal's sorted list or Prim's heap, cheapest first, each entry banded once it is kept or dropped. The lower strip plots the accepted weights in order: Kruskal's never fall, Prim's do. tree edges counts the accepted edges against the nodes minus one, weight their total, rejected the cycle-closing edges or stale entries,components the pieces still apart. Tap a waypoint to start Prim there.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The problem. A connected graph with $n$ nodes and a weight on every edge. A spanning tree is a set of edges that joins every node with no cycle; it always has exactly $n - 1$ edges, since each edge added to a cycle-free set joins two pieces into one and the graph starts as $n$ pieces. A minimum spanning tree has the least total weight among them. The traversal lessons built spanning trees too, the BFS and DFS trees, but those ignored weight.

The cut property. Split the nodes into any two non-empty groups, a cut. Let $e$ be a cheapest edge with one end in each group. Then some minimum spanning tree contains $e$ . Proof: take any minimum spanning tree $T$ without $e$ . Adding $e$ to $T$ closes a cycle, and that cycle must cross the cut at least once more, along some edge $f$ . Swap: $T - f + e$ is still a spanning tree, and since $w(e) \le w(f)$ its weight is no larger. Every greedy method on this stage is an application of this one fact.

Kruskal. Sort all the edges by weight. Walk the list; keep an edge if its ends are in different pieces of the forest so far, drop it if they are in the same piece, because it would close a cycle. When an edge is kept, its two pieces are the two sides of a cut, and the edge is the cheapest crossing it: every cheaper edge was looked at already and either lies inside a piece or was kept earlier. The piece question is the union-find's find, the merge its union, so the loop costs almost nothing and the sort dominates: $O(E \log E)$ , which is $O(E \log V)$ since $E < V^2$ .

Prim. Grow one tree from a start node. The cut is the tree against everything else, and the cheapest edge across it is found by a heap that holds every edge leaving the tree. Pop the cheapest; if its far end is already in the tree the entry is stale, left over from before that node joined by a cheaper route, and is dropped. Otherwise the edge joins, and the new node's edges go on the heap. Every edge is pushed at most once from each side, so the cost is $O((V + E) \log E)$ with a binary heap. Dijkstra's loop with one change: the priority is the edge's own weight, not the distance from the start.

Why the strips differ. Kruskal's accepted weights come off one sorted list, so the lower strip never falls. Prim's cheapest frontier edge is cheapest only among edges leaving the current tree; a later one can be cheaper than an earlier one, so Prim's strip rises and falls. Both totals agree, because both trees are built from cheapest cut edges, and when all weights are distinct the minimum spanning tree is unique, so they are the same tree. Ties are broken by the graph's edge order here, so two different trees of equal weight are possible on a graph with repeated weights.

Edges. On a disconnected graph the edges run out before $n - 1$ are accepted; the result is a minimum spanning forest, and the verdict says spanning: false. Prim started in a small component never leaves it. Negative weights are no trouble for either method; the cut property never asked for a sign.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

One class, two private methods. run dispatches on the algorithm name and both branches end in the same accept, the one moment they share, so the trace tag an edge joins on is the same tag whichever way it was found.
Kruskal sorts by (weight, index), so ties keep the graph's edge order and the run is deterministic; the sort emit carries the whole list once, which is what the upper strip draws.
The union-find is the one from its own lesson, UnionFind from the same library. find on both ends is traced as consider, and reject fires exactly when the two roots agree.
Prim's heap holds edges, not nodes, keyed by weight with the node reached as tiebreak. A node can be on it several times; the inTree flag catches the stale entries when they surface, the same lazy deletion Dijkstra uses.
Prim's accepted edges point from the tree side to the node that joined, so the order of from and to tells which end was new.
Both stop at nodeCount - 1 accepted edges rather than draining the list or the heap; the entries left behind are the edges never needed, and the verdict reports spanning by counting.

The problem was posed by an electricity company. In 1926 Otakar Boruvka of Brno was asked how to wire the towns of western Moravia into one grid with the least cable, and published the first algorithm in a Moravian journal, in Czech. Vojtech Jarnik answered in 1930 with the method that grows one tree from a single town. Unread in the West, it was solved again: by Joseph Kruskal in 1956, by Robert Prim at Bell Labs in 1957 for telephone networks, and by Edsger Dijkstra in 1959 in the paper that also gave his shortest-path algorithm. The stage names Kruskal and Prim; Prim's is Jarnik's.

1926Otakar Boruvka - Publishes 'O jistem problemu minimalnim' (On a certain minimal problem), the first minimum spanning tree algorithm, written to lay out an electrical network for western Moravia.source
1930Vojtech Jarnik - Replies to Boruvka in the same journal with the method that grows one tree from a start vertex by its cheapest outgoing edge, the algorithm later credited to Prim.source
1956Joseph Kruskal - 'On the shortest spanning subtree of a graph and the traveling salesman problem', three pages in the Proceedings of the American Mathematical Society: sort the edges, keep each one that closes no cycle.source
1957Robert C. Prim - 'Shortest connection networks and some generalizations' in the Bell System Technical Journal rediscovers Jarnik's method for laying out telephone networks.source
1959Edsger W. Dijkstra - 'A note on two problems in connexion with graphs' in Numerische Mathematik: the second problem is the spanning tree, found by the same grow-one-tree method, beside the shortest-path algorithm the paper is famous for.source

Used today

Network and circuit layout - The cheapest cable, pipe, or wire plan that reaches every site, which is the problem Boruvka and Prim were handed; chip routers use it as a first estimate of wire length.
Single-linkage clustering - Cut the k minus 1 heaviest edges out of the minimum spanning tree and the pieces are the k clusters of single-linkage clustering; the tree is the whole dendrogram.
Maze generation - Give every wall a random weight and run Kruskal: the walls it removes form a perfect maze, one path between any two cells, as the maze generation lesson shows.
Approximate travelling salesman tours - Walk the tree twice around and shortcut the repeats: a tour at most twice the optimum, the first step of Christofides' approximation.

Did you know

Boruvka's 1926 paper appeared in Czech in the journal of the Moravian Society of Natural Sciences, so the West did not read it; the method was rediscovered by Choquet in 1938, by a group of Polish mathematicians in 1951, and by Sollin in 1965, and is still sometimes called Sollin's algorithm.source
Kruskal and Prim were colleagues at Bell Laboratories, and Prim's 1957 paper acknowledges Kruskal's from the year before; the two methods that share a chip on this stage were published a year and a corridor apart.source
Dijkstra's 1959 paper is titled 'A note on two problems in connexion with graphs'. The problem everyone remembers is the shortest path; the other one, the spanning tree, made him the third person to publish Jarnik's method, which is why some books call it the DJP algorithm.source
The method usually called Prim's has at least four names: Jarnik's algorithm, the Prim-Jarnik algorithm, the Prim-Dijkstra algorithm, and DJP, for Dijkstra, Jarnik, and Prim.source

method

nodes12

radius3.0

start noden0

tree edges: 11 of 11
weight: 22.7
rejected: 3
components: 1

minimum-spanning-tree.ts

import type { Tracer } from "../trace";import { BinaryHeap } from "./binary-heap";import type { AdjacencyGraph, Edge } from "./graph";import { UnionFind } from "./union-find";export const MST_ALGORITHMS = ["kruskal", "prim"] as const;export type MstAlgorithm = (typeof MST_ALGORITHMS)[number];export interface MstResult {  /** The accepted edges in acceptance order; Prim's point from the tree side to the node it joined. */  readonly edges: readonly Edge[];  /** The sum of the accepted weights. */  readonly weight: number;  /** How many edges were accepted; `nodeCount - 1` on a spanning tree. */  readonly accepted: number;  /** Kruskal's cycle-closing rejects, or Prim's stale heap entries. */  readonly rejected: number;  /** Whether every node was reached; false on a forest, or for Prim's start in a smaller component. */  readonly spanning: boolean;  readonly algorithm: MstAlgorithm;}/** A heap entry in Prim's run: the frontier edge, read from the tree side. */interface Candidate {  from: number;  to: number;  weight: number;}/** * A minimum spanning tree of an undirected weighted graph, two ways. * * Kruskal sorts every edge by weight (ties by the edge's index, so the * order is the graph's) and takes each one whose ends sit in different * sets of a union-find, rejecting the ones that would close a cycle. * Prim grows one tree from a start node: every edge leaving the tree * waits in a binary heap by weight (ties by the node it reaches), the * cheapest is accepted, and an entry whose node joined the tree in the * meantime is stale and skipped. Both stop after `nodeCount - 1` * accepted edges; a disconnected graph runs out of edges first and the * result says `spanning: false`. Both find the same total weight, * because every accepted edge is a cheapest edge across some cut. * * Kruskal: O(E log E). Prim: O((V + E) log E). Space: O(V + E). */export class MinimumSpanningTree {  private edges: Edge[] = [];  private total = 0;  constructor(    readonly graph: AdjacencyGraph,    readonly algorithm: MstAlgorithm = "kruskal",    private readonly tracer?: Tracer,  ) {    if (graph.directed) throw new RangeError("a spanning tree needs an undirected graph");    if (!MST_ALGORITHMS.includes(algorithm)) throw new RangeError(`unknown algorithm ${String(algorithm)}`);  }  /** Builds the tree; `start` is where Prim begins, and Kruskal ignores it. */  run(start = 0): MstResult {    const n = this.graph.nodeCount;    if (!Number.isInteger(start) || start < 0 || start >= n) throw new RangeError(`start ${start} is not a node`);    this.edges = [];    this.total = 0;    const rejected = this.algorithm === "kruskal" ? this.kruskal() : this.prim(start);    const spanning = this.edges.length === n - 1;    // ▸ n - 1 edges and the least total weight, or a forest    this.tracer?.emit("verdict", { algorithm: this.algorithm, count: this.edges.length, spanning, weight: this.total });    return {      edges: this.edges,      weight: this.total,      accepted: this.edges.length,      rejected,      spanning,      algorithm: this.algorithm,    };  }  /** Cheapest edges first, each kept unless its ends are already joined; returns the reject count. */  private kruskal(): number {    const target = this.graph.nodeCount - 1;    const sorted = this.graph.edges      .map((edge, index) => ({ edge, index }))      .sort((a, b) => a.edge.weight - b.edge.weight || a.index - b.index)      .map(({ edge }) => ({ from: edge.from, to: edge.to, weight: edge.weight }));    // ▸ every edge, cheapest first; ties keep the graph's order    this.tracer?.emit("sort", { edges: sorted.map((edge) => ({ ...edge })) });    const sets = new UnionFind(this.graph.nodeCount);    const disjointSets = new UnionFind(this.graph.nodeCount);    let rejected = 0;    for (const { from, to, weight } of sorted) {      if (this.edges.length >= target) break;      const rootFrom = sets.find(from);      const rootFrom = disjointSets.find(from);      const rootTo = sets.find(to);      const rootTo = disjointSets.find(to);      // ▸ the cheapest edge left: are its ends in one set already?      this.tracer?.emit("consider", { from, rootFrom, rootTo, to, weight });      if (rootFrom === rootTo) {        rejected++;        // ▸ both ends share a root: this edge would close a cycle        this.tracer?.emit("reject", { from, root: rootFrom, to, weight });        continue;      }      sets.union(from, to);      disjointSets.union(from, to);      this.accept(from, to, weight);    }    return rejected;  }  /** One tree from `start`, grown by its cheapest frontier edge; returns the stale count. */  private prim(start: number): number {    const target = this.graph.nodeCount - 1;    const inTree: boolean[] = Array.from({ length: this.graph.nodeCount }, () => false);    const joined: boolean[] = Array.from({ length: this.graph.nodeCount }, () => false);    const heap = new BinaryHeap<Candidate>(    const frontierHeap = new BinaryHeap<Candidate>(      (c) => c.weight,      (c) => c.to,    );    let stale = 0;    inTree[start] = true;    joined[start] = true;    // ▸ prim begins here: the tree is one node and no edges    this.tracer?.emit("root", { node: start });    this.offer(start, inTree, heap);    this.offer(start, joined, frontierHeap);    while (heap.size > 0 && this.edges.length < target) {    while (frontierHeap.size > 0 && this.edges.length < target) {      const { from, to, weight } = heap.pop()!;      const { from, to, weight } = frontierHeap.pop()!;      if (inTree[to]) {      if (joined[to]) {        // Another edge reached this node first; the entry waited in the heap for nothing.        stale++;        // ▸ its node joined by a cheaper edge meanwhile: drop the entry        this.tracer?.emit("stale", { from, to, weight });        continue;      }      inTree[to] = true;      joined[to] = true;      this.accept(from, to, weight);      if (this.edges.length < target) this.offer(to, inTree, heap);      if (this.edges.length < target) this.offer(to, joined, frontierHeap);    }    return stale;  }  /** Pushes every edge from a tree node to a node outside it; an edge back into the tree is skipped. */  private offer(node: number, inTree: readonly boolean[], heap: BinaryHeap<Candidate>): void {  private offer(node: number, joined: readonly boolean[], frontierHeap: BinaryHeap<Candidate>): void {    for (const { to, weight } of this.graph.neighbors(node)) {      if (inTree[to]) {      if (joined[to]) {        // ▸ the neighbour is in the tree already: nothing to offer        this.tracer?.emit("skip", { from: node, to });        continue;      }      heap.push({ from: node, to, weight });      frontierHeap.push({ from: node, to, weight });      // ▸ a frontier edge waits on the heap, ordered by weight      this.tracer?.emit("push", { from: node, heap: heap.toArray().map((c) => ({ ...c })), to, weight });      this.tracer?.emit("push", { from: node, frontierHeap: frontierHeap.toArray().map((c) => ({ ...c })), to, weight });    }  }  /** The one moment both algorithms share: an edge joins the tree. */  private accept(from: number, to: number, weight: number): void {    this.edges.push({ from, to, weight });    this.total += weight;    // ▸ the edge joins the tree: one step closer to n - 1    this.tracer?.emit("accept", { count: this.edges.length, from, to, total: this.total, weight });  }}

edges =: 11
dropped =: 3
weight =: 22.7

11 edges accepted, 3 dropped, total weight 22.7.

import type { Tracer } from "../trace";import { BinaryHeap } from "./binary-heap";import type { AdjacencyGraph, Edge } from "./graph";import { UnionFind } from "./union-find";export const MST_ALGORITHMS = ["kruskal", "prim"] as const;export type MstAlgorithm = (typeof MST_ALGORITHMS)[number];export interface MstResult { /** The accepted edges in acceptance order; Prim's point from the tree side to the node it joined. */ readonly edges: readonly Edge[]; /** The sum of the accepted weights. */ readonly weight: number; /** How many edges were accepted; `nodeCount - 1` on a spanning tree. */ readonly accepted: number; /** Kruskal's cycle-closing rejects, or Prim's stale heap entries. */ readonly rejected: number; /** Whether every node was reached; false on a forest, or for Prim's start in a smaller component. */ readonly spanning: boolean; readonly algorithm: MstAlgorithm;}/** A heap entry in Prim's run: the frontier edge, read from the tree side. */interface Candidate { from: number; to: number; weight: number;}/** * A minimum spanning tree of an undirected weighted graph, two ways. * * Kruskal sorts every edge by weight (ties by the edge's index, so the * order is the graph's) and takes each one whose ends sit in different * sets of a union-find, rejecting the ones that would close a cycle. * Prim grows one tree from a start node: every edge leaving the tree * waits in a binary heap by weight (ties by the node it reaches), the * cheapest is accepted, and an entry whose node joined the tree in the * meantime is stale and skipped. Both stop after `nodeCount - 1` * accepted edges; a disconnected graph runs out of edges first and the * result says `spanning: false`. Both find the same total weight, * because every accepted edge is a cheapest edge across some cut. * * Kruskal: O(E log E). Prim: O((V + E) log E). Space: O(V + E). */export class MinimumSpanningTree { private edges: Edge[] = []; private total = 0; constructor( readonly graph: AdjacencyGraph, readonly algorithm: MstAlgorithm = "kruskal", private readonly tracer?: Tracer, ) { if (graph.directed) throw new RangeError("a spanning tree needs an undirected graph"); if (!MST_ALGORITHMS.includes(algorithm)) throw new RangeError(`unknown algorithm ${String(algorithm)}`); } /** Builds the tree; `start` is where Prim begins, and Kruskal ignores it. */ run(start = 0): MstResult { const n = this.graph.nodeCount; if (!Number.isInteger(start) || start < 0 || start >= n) throw new RangeError(`start ${start} is not a node`); this.edges = []; this.total = 0; const rejected = this.algorithm === "kruskal" ? this.kruskal() : this.prim(start); const spanning = this.edges.length === n - 1; // ▸ n - 1 edges and the least total weight, or a forest this.tracer?.emit("verdict", { algorithm: this.algorithm, count: this.edges.length, spanning, weight: this.total }); return { edges: this.edges, weight: this.total, accepted: this.edges.length, rejected, spanning, algorithm: this.algorithm, }; } /** Cheapest edges first, each kept unless its ends are already joined; returns the reject count. */ private kruskal(): number { const target = this.graph.nodeCount - 1; const sorted = this.graph.edges .map((edge, index) => ({ edge, index })) .sort((a, b) => a.edge.weight - b.edge.weight || a.index - b.index) .map(({ edge }) => ({ from: edge.from, to: edge.to, weight: edge.weight })); // ▸ every edge, cheapest first; ties keep the graph's order this.tracer?.emit("sort", { edges: sorted.map((edge) => ({ ...edge })) }); const sets = new UnionFind(this.graph.nodeCount); const disjointSets = new UnionFind(this.graph.nodeCount); let rejected = 0; for (const { from, to, weight } of sorted) { if (this.edges.length >= target) break; const rootFrom = sets.find(from); const rootFrom = disjointSets.find(from); const rootTo = sets.find(to); const rootTo = disjointSets.find(to); // ▸ the cheapest edge left: are its ends in one set already? this.tracer?.emit("consider", { from, rootFrom, rootTo, to, weight }); if (rootFrom === rootTo) { rejected++; // ▸ both ends share a root: this edge would close a cycle this.tracer?.emit("reject", { from, root: rootFrom, to, weight }); continue; } sets.union(from, to); disjointSets.union(from, to); this.accept(from, to, weight); } return rejected; } /** One tree from `start`, grown by its cheapest frontier edge; returns the stale count. */ private prim(start: number): number { const target = this.graph.nodeCount - 1; const inTree: boolean[] = Array.from({ length: this.graph.nodeCount }, () => false); const joined: boolean[] = Array.from({ length: this.graph.nodeCount }, () => false); const heap = new BinaryHeap<Candidate>( const frontierHeap = new BinaryHeap<Candidate>( (c) => c.weight, (c) => c.to, ); let stale = 0; inTree[start] = true; joined[start] = true; // ▸ prim begins here: the tree is one node and no edges this.tracer?.emit("root", { node: start }); this.offer(start, inTree, heap); this.offer(start, joined, frontierHeap); while (heap.size > 0 && this.edges.length < target) { while (frontierHeap.size > 0 && this.edges.length < target) { const { from, to, weight } = heap.pop()!; const { from, to, weight } = frontierHeap.pop()!; if (inTree[to]) { if (joined[to]) { // Another edge reached this node first; the entry waited in the heap for nothing. stale++; // ▸ its node joined by a cheaper edge meanwhile: drop the entry this.tracer?.emit("stale", { from, to, weight }); continue; } inTree[to] = true; joined[to] = true; this.accept(from, to, weight); if (this.edges.length < target) this.offer(to, inTree, heap); if (this.edges.length < target) this.offer(to, joined, frontierHeap); } return stale; } /** Pushes every edge from a tree node to a node outside it; an edge back into the tree is skipped. */ private offer(node: number, inTree: readonly boolean[], heap: BinaryHeap<Candidate>): void { private offer(node: number, joined: readonly boolean[], frontierHeap: BinaryHeap<Candidate>): void { for (const { to, weight } of this.graph.neighbors(node)) { if (inTree[to]) { if (joined[to]) { // ▸ the neighbour is in the tree already: nothing to offer this.tracer?.emit("skip", { from: node, to }); continue; } heap.push({ from: node, to, weight }); frontierHeap.push({ from: node, to, weight }); // ▸ a frontier edge waits on the heap, ordered by weight this.tracer?.emit("push", { from: node, heap: heap.toArray().map((c) => ({ ...c })), to, weight }); this.tracer?.emit("push", { from: node, frontierHeap: frontierHeap.toArray().map((c) => ({ ...c })), to, weight }); } } /** The one moment both algorithms share: an edge joins the tree. */ private accept(from: number, to: number, weight: number): void { this.edges.push({ from, to, weight }); this.total += weight; // ▸ the edge joins the tree: one step closer to n - 1 this.tracer?.emit("accept", { count: this.edges.length, from, to, total: this.total, weight }); }}