△ Prim's MST Algorithm

Start here (middle school). Imagine wiring up a new neighborhood. One house already has power, and you must connect every other house using the least total cable. The natural move: look at all the houses already connected, find the single cheapest wire that reaches a brand-new house, lay it, and repeat. You never design the whole network at once — you just keep grabbing the cheapest wire that grows your connected cluster by one house. That is Prim's algorithm.

Name the pieces (high school). A network is a graph of $V$ vertices (houses) joined by weighted edges (cables of cost $w$). Prim's keeps a growing tree of connected vertices and, for every vertex $v$ still outside, a number $key[v]$ = the cheapest single edge that would attach $v$ to the current tree. Each round you pick the outside vertex with the smallest $key$, pull it in, and refresh its neighbors' keys.

One worked example. Start at A with edges A–B $= 4$, A–C $= 1$, B–C $= 2$. The cheapest edge leaving A is A–C $= 1$, so C joins first. Now B can attach through A–B $= 4$ or the cheaper C–B $= 2$, so $key[B]$ drops to $2$. Add B–C $= 2$. Total cost $= 1 + 2 = 3$, using exactly $V-1 = 2$ edges — the minimum spanning tree.

Why it is correct (AP / college). At every step the connected set and the outside set form a cut. The minimum-weight edge crossing any cut is always safe to add to some MST — the Cut Property. Prim's smallest-$key$ pick is exactly that minimum crossing edge, so it never errs. The update rule applied to each neighbor whenever a new vertex $u$ joins is $$key[v] \leftarrow \min\bigl(key[v],\; w(u,v)\bigr).$$ With a binary-heap priority queue the cost is $O((V+E)\log V) = O(E\log V)$; with a plain array scan it is $O(V^2)$, which actually wins on dense graphs where $E \approx V^2$.

Try this in the panel above. (1) Drag the $n$ slider from small to large and watch the Comparisons counter climb — that super-linear growth is the same scaling that separates $O(V^2)$ from $O(E\log V)$. (2) Switch between the Sorted and Reverse presets to compare best- and worst-case operation counts. (3) Tap ▶│ to advance one move at a time and watch a greedy method commit to a single cheapest choice each round — exactly how Prim's commits to one cheapest edge per step.

Step 1 -- Grow from a Seed. Prim's grows the MST one vertex at a time from a starting vertex. key[v] = minimum weight edge connecting v to the current MST. Always add the vertex with smallest key (minimum cut edge).

Step 2 -- Correctness via Cut Property. At each step, the current MST tree defines a cut (MST vertices vs non-MST vertices). The vertex with minimum key represents the minimum weight edge crossing this cut. By the Cut Property, this edge is in some MST.

Step 3 -- Time with Binary Heap. V extract-min: O(V log V). E decrease-key: O(E log V). Total: O((V+E) log V) = O(E log V) for connected graphs.

Step 4 -- Time with Simple Array. Find min-key vertex by scanning all V vertices: O(V). Done V times: O(V^2). Update keys: O(E). Total: O(V^2). Better than heap for dense graphs (E = O(V^2)).

Step 5 -- vs Kruskal. Prim: starts from a vertex, grows tree greedily. Better for dense graphs with adjacency matrix O(V^2). Kruskal: sorts all edges globally. Better for sparse graphs O(E log E). Both give valid MST.

Step 6 -- MST Weight Recovery. Sum of all key[] values (after algorithm) = total MST weight. Or sum edge weights as they are added. MST edges: (parent[v], v) for all v != start.