Prim and Kruskal: two ways to build a minimum spanning tree

What the two algorithms minimize

A minimum spanning tree connects all vertices of a connected undirected weighted graph without cycles, minimizing the total weight of its edges. It contains V−1 edges. This is a network design problem: it does not minimize every route from a start vertex. On a disconnected graph, our implementations return a minimum spanning forest with V−C edges, where C is the number of connected components.

Prim has a chosen start vertex. At each choice it takes a cheapest edge crossing from the visited set to an unvisited vertex. Kruskal has no start: it sorts every edge by weight, then accepts an edge only when its endpoints belong to different components.

One graph, different choices

On the default graph, Prim starts at A and takes A—C (2), B—C (1), C—E (5), D—E (2). Kruskal takes B—C (1), A—C (2), D—E (2), skips A—B (4) because it would close a cycle, then adds C—E (5). The selected edge set is the same and its total is 10.

The third choice makes the difference visible: Prim must connect its growing tree to E via C—E (5). The cheaper D—E (2) is outside its boundary. Kruskal can already take D—E, forming a separate tree. Move Prim’s start to D or E and compare the order again. Kruskal’s run stays unchanged.

Why both choices are safe

The cut property explains both strategies: a minimum-weight edge crossing a cut that respects the chosen forest is safe to add to some minimum spanning forest. Prim uses the cut between visited and unvisited vertices. Kruskal uses the cut around a current component; an edge with both endpoints in that component would create a cycle.

Neither algorithm needs nonnegative weights. This is a different task from Dijkstra’s shortest-path algorithm. Connectivity and absence of cycles constrain the forest even when an edge weight is negative.

Equal, negative and missing edges

Try Equal weights: ties can allow different optimal trees. The player breaks ties by the original edge index so every run can be reproduced. Changing Prim’s start can change its tree, but not the minimum total. A different edge set does not by itself mean an algorithm is wrong.

Negative and zero weights changes B—C to −3 and D—E to 0; both results have total 4. The disconnected example has two final trees, three edges and total 5. Prim restarts at the first unvisited vertex after exhausting a component; Kruskal continues merging wherever an edge permits. An isolated vertex is also a component. One vertex needs no edges.

Read the comparison correctly

Blue P lines belong to Prim; green K lines belong to Kruskal. When both select an edge, two parallel colored lines remain visible. Long dashes and a P/K marker indicate the current candidate. Prim’s other boundary edges are dotted; Kruskal’s rejected cycle edges use short dashes. The controls can isolate either algorithm’s lines while preserving the shared run.

Each animation round has two phases: inspect one candidate for each unfinished algorithm, then apply both decisions together. A completed algorithm holds its final state. Starting a new Prim component and sorting Kruskal’s edges are not timed operations here. The tick count and wall-clock duration are not benchmarks. Partial totals can differ; compare final totals after both algorithms finish.

The cards expose accepted edges in order, selected-forest components including isolated vertices, and the current decision. Changing a weight, preset or Prim’s start restarts both histories. Share preserves the input, start, visible lines, tick and speed on a paused clean player page. Save video exports the full run with the selected line view, without audio.

Complexity of these implementations

Prim in this demo scans all E edges to choose a crossing minimum and also scans at the end of each component: O(VE+V) time and O(V+E) working storage including graph validation/copying. A heap-based implementation with adjacency lists can achieve O(E log V) on connected graphs; this player does not implement that variant.

Kruskal sorts E edges, then uses union by size and path compression: O(V + E log(E+1) + E α(V)) time and O(V+E) working storage including graph copies. Its displayed edge decisions omit sorting comparisons and DSU operations. The two models’ internal counters therefore cannot be compared as equal units of work.

Visualization history costs extra. Prim copies the selected edges, visited set and boundary for each frame; Kruskal copies selected/rejected edges and component labels. The comparison reuses immutable snapshots from both models. With P and K recorded frames, a safe history bound is O((P+K)(V+E)), separate from the algorithms’ working space.

Executable code

These are the same result-producing functions used in the individual Prim and Kruskal articles. Their edge indices match the input array. The player adds immutable snapshots and aligns the candidate/decision phases for teaching; it does not substitute a second MST implementation.

function prim(n, edges, start = 0) {
  if (!Number.isInteger(n) || n < 1 || !Number.isInteger(start) ||
      start < 0 || start >= n || !Array.isArray(edges)) throw Error("Invalid graph");
  const valid = v => Number.isInteger(v) && v >= 0 && v < n;
  let bound = 0;
  for (const e of edges) {
    if (!e || !valid(e.from) || !valid(e.to) || e.from === e.to ||
        !Number.isSafeInteger(e.weight)) throw Error("Invalid edge");
    bound += Math.abs(e.weight);
    if (!Number.isSafeInteger(bound)) throw Error("Unsafe weight sum");
  }
  const seen = Array(n).fill(false), selected = [];
  let weight = 0, components = 0;
  const roots = [start, ...Array.from({length: n}, (_, i) => i).filter(i => i !== start)];
  for (const root of roots) {
    if (seen[root]) continue;
    seen[root] = true;
    components++;
    while (true) {
      let best = -1;
      for (let i = 0; i < edges.length; i++) {
        const e = edges[i];
        if (seen[e.from] === seen[e.to]) continue;
        if (best === -1 || e.weight < edges[best].weight) best = i;
      }
      if (best === -1) break;
      const e = edges[best];
      seen[e.from] = seen[e.to] = true;
      selected.push(best);
      weight += e.weight;
    }
  }
  return { edges: selected, weight, components };
}

function kruskal(n, edges) {
    if (!Number.isInteger(n) || n < 1 || !Array.isArray(edges))
        throw new RangeError("Invalid graph");
    let budget = 0;
    const pairs = new Set();
    for (const e of edges) {
        if (!e || !Number.isInteger(e.from) || !Number.isInteger(e.to) ||
            e.from < 0 || e.from >= n || e.to < 0 || e.to >= n ||
            e.from === e.to || !Number.isSafeInteger(e.weight))
            throw new RangeError("Invalid edge");
        const key = [e.from, e.to].sort((a, b) => a - b).join(":");
        if (pairs.has(key)) throw new RangeError("Duplicate edge");
        pairs.add(key);
        budget += Math.abs(e.weight);
        if (!Number.isSafeInteger(budget)) throw new RangeError("Unsafe sum");
    }
    const order = edges.map((_, id) => id)
        .sort((a, b) => edges[a].weight - edges[b].weight || a - b);
    const parent = Array.from({ length: n }, (_, i) => i);
    const size = Array(n).fill(1);
    function find(v) {
        while (v !== parent[v]) {
            parent[v] = parent[parent[v]];
            v = parent[v];
        }
        return v;
    }
    const selected = [];
    let weight = 0, components = n;
    for (const id of order) {
        if (components === 1) break;
        const e = edges[id];
        let a = find(e.from), b = find(e.to);
        if (a === b) continue;
        if (size[a] < size[b]) [a, b] = [b, a];
        parent[b] = a;
        size[a] += size[b];
        selected.push(id);
        weight += e.weight;
        components--;
    }
    return { edges: selected, weight, components };
}