Interactive Lab · DSA & Algorithms
You have to lay fibre between a set of cities. Every possible link has a cost, and you need every city connected, directly or through others, for the least total cost. The answer is a minimum spanning tree (MST): exactly n − 1 edges, no cycles, smallest possible sum. Two famous greedy algorithms find it. Kruskal sorts every edge cheapest first and takes each one unless it would close a loop. Prim grows a single tree from one city, always grabbing the cheapest edge leaving it. They look nothing alike. Step through both on the same graph and check the totals.
The setup, a weighted graph and one goal
Each circle is a city, each line a possible link, and the number on a line is its cost. A spanning tree touches every city using n − 1 links with no cycle; the minimum one has the smallest total cost.
Both algorithms are greedy: they never undo a choice. The surprise is that greedy is provably optimal here, by the cut property: for any split of the cities into two groups, the cheapest link crossing the split is always safe to take.
▶ The playground, pick an algorithm, then step it
Minimum spanning trees are the cheapest way to connect things: laying power lines, water pipes, road and fibre networks; designing circuit-board wiring; and, in machine learning, single-linkage clustering (build the MST, cut its most expensive edges, and what's left are the clusters). Kruskal is built on the Union-Find lab's cycle check; Prim is Dijkstra with one line changed. In placement rounds it shows up as "Min Cost to Connect All Points" and "Connecting Cities With Minimum Cost".
The code that's actually running, flip the algorithm to see the other
Run Kruskal to the end and note the total weight. Now switch to Prim, change the start city, and run it again. Predict before you press play: will Prim's total be smaller, larger or equal? Try a few new graphs. Then tick compare with shortest paths: is the route between two cities inside the MST always the cheapest route between them? Why not, if the tree is "minimum"?
The takeaway
E edges, then take each one whose ends are in different components, which a union-find answers in almost O(1). Total O(E log E), dominated by the sort. Great for sparse graphs given as an edge list.O(E log V), and natural for adjacency lists and dense graphs.