Pattern visualizer
Prim's Algorithm (MST)
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. 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..
Grow one tree outward, always absorbing the cheapest edge crossing the cut
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.
1FUNCTION primMST(n, edges):2 minDist[0..n-1] <- INFINITY3 minDist[0] <- 04 visited[0..n-1] <- FALSE5 total <- 06 FOR i FROM 1 TO n7 u <- UNVISITED VERTEX WITH MIN minDist8 visited[u] <- TRUE9 total <- total + minDist[u]10 FOR EACH (v, w) IN ADJACENT(u)11 IF NOT visited[v] AND w < minDist[v]12 minDist[v] <- w13 RETURN total
← / → step · space play · Home restart