DSA Tracker

Visualize

Minimum Spanning Tree (Prim's)

Grow one tree outward, always absorbing the cheapest edge crossing the cut

time O(V^2)space O(V)

Grow the tree outward like a crystal starting from an arbitrary seed vertex — here vertex 0. Track one number per outside vertex: its cheapest known distance to the current tree. At every step the cut property guarantees the outside vertex with the smallest such distance is safe to absorb, so repeatedly picking that minimum and then re-checking its neighbours' distances builds the MST without ever having to reason about cycles.

Details

Animated on: n = 4 vertices, edges [[0,1,1],[0,2,4],[1,2,2],[1,3,6],[2,3,3]] — find the minimum spanning tree's total weight using Prim's algorithm.

Problem:Minimum Spanning Tree (Prim's)Medium

Grow one tree outward, always absorbing the cheapest edge crossing the cut

step 1 / 9

Weighted graph — build the minimum spanning tree from vertex 0

4 vertices, 5 weighted edges. A spanning tree needs 3 edges that touch every vertex with no cycle; the MINIMUM one is the cheapest such set. Prim's grows one tree outward, always absorbing the cheapest edge that crosses from the tree into the outside.

Pseudocode
1FUNCTION primMST(n, edges):
2  minDist[0..n-1] <- INFINITY
3  minDist[0] <- 0
4  visited[0..n-1] <- FALSE
5  total <- 0
6  FOR i FROM 1 TO n
7    u <- UNVISITED VERTEX WITH MIN minDist
8    visited[u] <- TRUE
9    total <- total + minDist[u]
10    FOR EACH (v, w) IN ADJACENT(u)
11      IF NOT visited[v] AND w < minDist[v]
12        minDist[v] <- w
13  RETURN total

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. 4 vertices, 5 weighted edges. A spanning tree needs 3 edges that touch every vertex with no cycle; the MINIMUM one is the cheapest such set. Prim's grows one tree outward, always absorbing the cheapest edge that crosses from the tree into the outside.
  2. Start the cut at vertex 0 — nothing is in the tree yet, so it is free (distance 0) and the only candidate.
  3. Absorbing 0 opens 2 new edges into the cut: vertex 1 at 1, vertex 2 at 4.
  4. Vertex 1 sits at distance 1 from the tree via vertex 0, the cheapest of everything still outside. Pop it off the frontier.
  5. Add edge 0-1 (weight 1) to the tree — running total is now 1. Absorbing 1 also cheapens the route to vertex 2 (4 → 2), vertex 3 (first route, 6).
  6. Vertex 2 sits at distance 2 from the tree via vertex 1, the cheapest of everything still outside. Pop it off the frontier.
  7. Add edge 1-2 (weight 2) to the tree — running total is now 3. Absorbing 2 also cheapens the route to vertex 3 (6 → 3).
  8. Vertex 3 sits at distance 3 from the tree via vertex 2, the cheapest of everything still outside. Pop it off the frontier.
  9. Add edge 2-3 (weight 3) to the tree — running total is now 6. Every vertex is now in the tree.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Minimum Spanning Tree (Prim's) in the editorAll Graph problemsBack to roadmap