Prim’s algorithm: minimum spanning tree

A network, rather than a route

An undirected edge works in both directions. A spanning tree includes every vertex and has no cycles; on V vertices it has V−1 edges. Its weight is the sum of its edge weights. We minimize this sum, without requiring the route from the start to each vertex to be shortest.

The start only determines the order of growth. With equal weights, another start can produce a different minimum tree with the same total weight. A disconnected graph has no single spanning tree; this player builds a minimum spanning forest, one tree per connected component, including isolated vertices.

Choose across the whole boundary

Mark one vertex as included. Consider every edge with exactly one included endpoint: these edges cross the boundary between the current tree and the remaining vertices. Choose one of minimum weight and add its other endpoint. An edge entirely inside the tree would create a cycle; an edge with both endpoints outside cannot extend this tree yet.

This is not a walk from the last added vertex. All crossing edges compete together. The implementation scans the original edge list and keeps the first minimum when weights tie. An equally light edge is also valid; tie-breaking makes this demonstration reproducible.

Five vertices, total weight ten

From A, compare A—B = 4 and A—C = 2. Add A—C. The next boundary contains A—B = 4, C—B = 1, C—D = 8 and C—E = 5. Add C—B = 1, although B is not reached directly from the start.

Next add C—E = 5, even though B was added last: all crossing edges compete, including those from C. Then add E—D = 2. The result has four edges and weight 2 + 1 + 5 + 2 = 10. D—E = 2 was cheap from the beginning, but initially neither endpoint belonged to the tree. Edge weights need not increase in the order selected.

Why the local choice is safe

The maintained forest can always be extended to a minimum spanning forest. For a connected component, consider a minimum tree containing all edges selected so far. If it lacks the chosen crossing edge, adding that edge creates a cycle. The cycle contains another crossing edge, whose weight cannot be smaller. Exchange those edges: connectivity remains, no cycle remains and the total weight does not increase.

Thus at least one minimum tree still contains every selected edge. A step adds one previously excluded vertex, so selected edges never form a cycle. When no crossing edge remains, the whole current component is included; the next unmarked vertex starts another component. The final forest has V−C edges, where C is the number of connected components.

Equal, zero and negative weights

Prim accepts all three. It compares edge weights directly, without accumulating tentative route distances as Dijkstra does. Negative weights therefore do not invalidate the rule. We still seek an acyclic spanning structure, not the cheapest arbitrary subgraph: even a negative edge is not added if it would close a cycle.

The equal-weight preset makes every edge weigh one: any spanning tree of a component has the same weight. The negative preset changes B—C to −3 and D—E to zero; the minimum total becomes four. Try a different start and compare the final totals.

Read and control the player

Green edges and vertices belong to the forest. Blue dashed lines show all currently crossing edges, with the selected minimum highlighted in amber. Grey edges are currently ineligible. The candidate set appears as one stage; the next stage adds its chosen edge. The same information is available in text below the canvas.

Change the example, start or an edge weight. Invalid input preserves the current valid run. This demo accepts 1–8 uniquely labelled vertices, at most 28 undirected edges without loops or duplicate unordered pairs, and integer weights from −99 to 99. Zero is a real weight, not an absent edge. Use the shared controls to step, rewind, change speed, enter fullscreen, share a paused clean player page or save a silent video.

This implementation and its saved history

For clarity, each boundary is found by scanning all E edges. Each added vertex is followed by one scan, including the final empty boundary of each component: V full scans in total, or VE edge inspections. Time is O(VE + V), and working memory is O(V) apart from the input and returned forest. A heap-based Prim implementation has different bounds; those do not describe this scan-based demo.

The player additionally stores O(V) immutable snapshots, each with visited vertices, selected edges and up to E crossing edges. History uses O(V(V+E)) memory, with one shared O(V+E) graph. Playback duration illustrates decisions and does not benchmark computation speed.

JavaScript implementation

The function below returns edge indices, total weight and component count without animation history. It uses the same full scans, edge-order tie-breaking and component restart as the player. Endpoint indices run from zero to n−1. Safe integer weights and their absolute sum are validated to prevent arithmetic overflow; the player imposes smaller bounds for readable scenes.

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 };
}