Prim's Algorithm Visualizer

You have a set of towns and a list of possible cable routes between them, each with a cost. You need every town connected, and you want to spend as little as possible. That is the minimum spanning tree problem, and Prim's algorithm solves it by growing a single connected blob outward: start anywhere, and repeatedly absorb whichever town is cheapest to reach from what you already have.

It is the same greedy shape as Dijkstra's algorithm, with one crucial difference that people mix up constantly. Dijkstra asks *how far is this node from the source*; Prim asks *how cheap is this node to attach to the tree*. One accumulates a total distance, the other looks at a single edge weight. Change that one comparison and you change which problem you are solving.

What is Prim's algorithm?

A spanning tree of a connected graph is a subset of edges that connects every vertex with no cycles. It always has exactly V−1 edges. A minimum spanning tree is the spanning tree whose edges sum to the lowest total weight.

Prim's algorithm builds one incrementally. It starts with an arbitrary vertex as a one-node tree, then repeatedly finds the cheapest edge crossing from the tree to a vertex outside it, and adds that edge and vertex. After V−1 such additions every vertex is included and the tree is complete.

The key structural property is that the tree is always connected. At every point in the algorithm you have one growing blob, never several fragments. Kruskal's algorithm solves the same problem the opposite way — accumulating a forest of disconnected pieces that eventually merge — and that difference in structure is what makes each better suited to different graphs.

Why the greedy choice is safe

The justification is the cut property: for any partition of the vertices into two non-empty sets, the cheapest edge crossing between them belongs to some minimum spanning tree. This one fact is the entire correctness argument for both Prim's and Kruskal's algorithms.

The proof is a swap argument. Let e be the cheapest edge crossing the cut, and suppose some MST T does not contain it. Adding e to T creates exactly one cycle, and that cycle must cross the cut a second time via some other edge f — you cannot leave one side and stay away. Since e is the cheapest crossing edge, weight(e) ≤ weight(f). Removing f and adding e gives another spanning tree of weight no greater than T's, so it is also minimum, and it contains e.

Prim's algorithm applies this at every step with the cut being 'vertices in the tree' versus 'vertices outside it'. Each edge it adds is the cheapest crossing that cut, so each is safe. After V−1 safe additions, the result is a minimum spanning tree.

Step-by-step walkthrough

A graph with A–B cost 2, A–C cost 3, B–C cost 1, B–D cost 4, C–D cost 5. Start at A.

1. Tree = {A}. Candidate edges leaving the tree: A–B at 2, A–C at 3. Cheapest is A–B.
2. Add A–B. Tree = {A, B}. Candidates now: A–C at 3, B–C at 1, B–D at 4. Cheapest is B–C at 1.
3. Add B–C. Tree = {A, B, C}. Note that A–C at 3 is now useless — both endpoints are inside the tree, so it would create a cycle. Remaining candidates: B–D at 4, C–D at 5.
4. Add B–D at 4. Tree = {A, B, C, D}, with three edges for four vertices. Done.
5. Total weight 2 + 1 + 4 = 7. The MST uses A–B, B–C and B–D, and deliberately skips the direct A–C edge even though it connects two tree members.

Prim or Kruskal?

Both produce a minimum spanning tree — the same total weight, though possibly different edge sets when weights tie. The choice is about graph density and data structures.

Prim wins on dense graphs. With an adjacency matrix and a simple array-based selection it runs in O(V²), which is optimal when E approaches V² because you cannot do better than examining every edge once. With a binary heap it is O(E log V).

Kruskal wins on sparse graphs. It runs in O(E log E), dominated by sorting the edges, which is cheap when E is small relative to V². It also does not need an adjacency structure at all — just a list of edges, which is often exactly how graph data arrives.

There is a practical difference too. Kruskal needs to sort all edges up front, so it must see the whole graph before it starts. Prim only needs to know the neighbours of the tree it has grown so far, which makes it usable when the graph is discovered incrementally. And Kruskal requires a union-find structure; Prim requires a priority queue. Whichever you already have is a legitimate tiebreaker.

How the animation above works

The candidate list shows the frontier — every edge leaving the current tree — sorted so the cheapest is first. Watch what happens to an edge whose far endpoint gets absorbed by a different route: it silently stops being a candidate, because both its endpoints are now inside the tree and adding it would close a cycle.

The visual difference from Kruskal is the thing to notice. Prim's mint edges always form one connected blob growing outward from the start node. Run Kruskal on the same graph and you will see disconnected mint fragments appear all over the canvas before they eventually join up. Same total weight, entirely different construction order.

Change the start node and re-run. The tree that results is usually the same set of edges, because the MST is a property of the graph rather than of where you begin — unless several edges share a weight, in which case ties can break differently.

Time and space complexity

O(V²) with an adjacency matrix and linear-scan selection. This is the right choice for dense graphs, and it is why Prim is often preferred over Kruskal there — no heap, no sorting, no allocation.

O(E log V) with a binary heap and adjacency lists, which is the standard implementation for sparse graphs. Each edge may trigger a heap operation and each vertex is extracted once.

O(E + V log V) with a Fibonacci heap, matching Dijkstra's theoretical optimum. As with Dijkstra, the constant factors mean this rarely wins in practice.

O(V) space for the key array, parent array and in-tree set, plus the priority queue — which can reach O(E) if you use lazy insertion rather than decrease-key.

What minimum spanning trees are actually for

The textbook framing is network cabling, and that is genuine — laying fibre, water pipes or power lines between a set of locations at minimum total cost is exactly the problem. But the more common uses today are indirect.

Clustering. Build the MST, then delete the k−1 most expensive edges. What remains is k connected components, and this is precisely single-linkage hierarchical clustering. It is a clean, parameter-light clustering method that falls straight out of the MST.

Approximation algorithms. The travelling salesman problem is NP-hard, but walking an MST twice gives a tour at most twice the optimal length — a 2-approximation in polynomial time. Christofides' algorithm refines the same idea to 1.5.

Image segmentation and computer vision, where pixels form a graph weighted by colour difference and the MST separates regions.

Network design and reliability, including broadcast trees that reach every node with minimum total link cost, and circuit design minimising total wire length.

Complexity at a glance

The numbers below are what the counters in the visualiser converge on. Raise the array size and watch the comparison count grow at the rate this table predicts.

Pseudo code

Language-agnostic, and close enough to the implementations below that you can read them side by side.

Prim's Algorithm in five languages

Working reference implementations — copy or download any of them. They are written to be read, so the comments explain the decisions rather than restating the code.

/**
 * Prim's algorithm with a simple sorted-array frontier.
 *
 * The critical line is the comparison in the relaxation: it uses the edge
 * weight alone, not a running total. Using a running total would give you
 * Dijkstra's shortest-path tree instead of a minimum spanning tree.
 */
function prim(graph, start) {
  const inTree = new Set([start]);
  const mstEdges = [];
  let totalWeight = 0;

  // Candidate edges leaving the tree. A heap is better; this is clearer.
  let frontier = (graph.get(start) ?? []).map(([to, weight]) => ({
    from: start,
    to,
    weight,
  }));

  while (inTree.size < graph.size && frontier.length > 0) {
    frontier.sort((a, b) => a.weight - b.weight);
    const edge = frontier.shift();

    // Both endpoints already inside? Adding it would close a cycle.
    if (inTree.has(edge.to)) continue;

    inTree.add(edge.to);
    mstEdges.push(edge);
    totalWeight += edge.weight;

    for (const [to, weight] of graph.get(edge.to) ?? []) {
      if (!inTree.has(to)) frontier.push({ from: edge.to, to, weight });
    }
  }

  return { mstEdges, totalWeight };
}

const graph = new Map([
  ["A", [["B", 2], ["C", 3]]],
  ["B", [["A", 2], ["C", 1], ["D", 4]]],
  ["C", [["A", 3], ["B", 1], ["D", 5]]],
  ["D", [["B", 4], ["C", 5]]],
]);

console.log(prim(graph, "A")); // total weight 7

Advantages and disadvantages

Real-world applications

• Network infrastructure design — laying cable, fibre, pipelines or power lines to connect all sites at minimum total cost.
• Single-linkage hierarchical clustering, by building the MST and cutting its k−1 most expensive edges.
• Approximation algorithms for the travelling salesman problem, where an MST traversal gives a tour within twice the optimum.
• Image segmentation, treating pixels as vertices weighted by colour or intensity difference.
• Circuit and chip design, minimising total wire length across a set of connection points.
• Broadcast and multicast tree construction in networks, reaching every node at minimum total link cost.
• Maze generation, where a random-weight MST over a grid graph produces a perfect maze with exactly one path between any two cells.

Interview questions

The questions that actually get asked about Prim's Algorithm, with the answers an interviewer is listening for.

1. Q1. What is the difference between Prim's algorithm and Dijkstra's?

   One comparison. Dijkstra relaxes with distance[u] + weight, accumulating total cost from the source, and produces a shortest-path tree. Prim compares weight alone — the cost of a single edge attaching a vertex to the tree — and produces a minimum spanning tree. The two trees are usually different: Dijkstra's minimises each node's distance from one source, while Prim's minimises the total weight of all edges used.

2. Q2. Why is Prim's greedy choice correct?

   The cut property: for any partition of the vertices, the cheapest edge crossing between the two sides belongs to some MST. The proof is a swap argument — adding that edge to any MST that lacks it creates a cycle which must cross the cut a second time, and exchanging the more expensive crossing edge for the cheaper one yields a spanning tree no heavier than the original. Prim applies this repeatedly with the cut being 'in the tree' versus 'outside it'.

3. Q3. When would you choose Prim over Kruskal?

   On dense graphs, where Prim's O(V²) adjacency-matrix form beats Kruskal's O(E log E) — with E near V², sorting the edges is the dominant cost. Prim is also preferable when the graph arrives as an adjacency structure rather than an edge list, when you need the tree to stay connected as it grows, or when the graph is being discovered incrementally and cannot be sorted up front.

4. Q4. Does the choice of starting vertex change the resulting MST?

   Not the total weight, which is a property of the graph. The specific edge set can differ if several edges share the same weight, since ties may break differently from different starting points. If all edge weights are distinct, the MST is unique and every starting vertex produces exactly the same tree.

5. Q5. How would you find a maximum spanning tree?

   Negate every edge weight and run Prim's algorithm unchanged — the cheapest edge in the negated graph is the most expensive in the original. Alternatively, replace the min-heap with a max-heap. The cut property has a symmetric form for maximum spanning trees, so the correctness argument carries over directly.

Common mistakes

• Writing the relaxation as key[u] + weight instead of weight, which silently turns Prim into Dijkstra and produces a shortest-path tree.
• Forgetting to check whether an edge's far endpoint is already in the tree, which adds cycle-forming edges and breaks the tree property.
• Using a max-heap instead of a min-heap — in C++, omitting std::greater on the priority queue.
• Assuming the algorithm covers a disconnected graph, when it only spans the component containing the start vertex.
• Adding every incident edge to the frontier without filtering, so the heap fills with edges whose endpoints are both already inside.
• Stopping when the heap empties rather than when V−1 edges have been added, which silently returns an incomplete tree on a disconnected graph.
• Using the heap implementation on a dense graph, where the simple O(V²) array version is measurably faster.

Optimisation tips

• Use the O(V²) array implementation on dense graphs — no heap, no allocation, and it is genuinely faster when E approaches V².
• Use an indexed heap with real decrease-key if memory matters; otherwise lazy insertion with a stale-entry check is simpler and just as fast asymptotically.
• Stop as soon as V−1 edges have been added rather than draining the heap.
• Skip edges whose far endpoint is already in the tree at insertion time, not just at extraction time, to keep the heap smaller.
• For a maximum spanning tree, negate the weights rather than writing a second implementation.
• For very large sparse graphs, consider Borůvka's algorithm instead, which parallelises far better than either Prim or Kruskal.

Summary

Prim's algorithm builds a minimum spanning tree by growing a single connected component outward from an arbitrary start vertex, repeatedly absorbing whichever vertex is cheapest to attach. Its correctness follows from the cut property: the cheapest edge crossing any partition of the vertices belongs to some MST.

It runs in O(V²) with an adjacency matrix — the right choice for dense graphs — or O(E log V) with a binary heap for sparse ones, where Kruskal is usually faster. The single most important thing to get right is the comparison: Prim uses the edge weight alone, while Dijkstra uses the accumulated distance. The implementations differ by that one expression and solve genuinely different problems.

Frequently asked questions

Related algorithms

• Kruskal's Algorithm

  Sort every edge by weight and add the cheap ones that don't close a cycle.

  O(E log E)Advanced

• Dijkstra's Algorithm

  Greedily settle the nearest unvisited node to get shortest paths on non-negative weights.

  O((V + E) log V)Advanced

• Breadth-First Search

  Explore a graph level by level with a queue — the shortest path on unweighted edges.

  O(V + E)Intermediate