Minimum Spanning Tree Builder Screensaver
The Minimum Spanning Tree Builder screensaver runs a real live Prim's algorithm over a random point cloud, connecting every point with the cheapest possible total edge length. It is free, runs in your browser, and ESC exits.
Live preview
Press ESC to leave fullscreen. Settings are saved in your browser only.
How the Minimum Spanning Tree Builder screensaver works
The saver scatters a real random cloud of points, then runs Prim's algorithm to connect them all with a minimum spanning tree.
Each step adds the real cheapest edge that connects a new point to the growing tree, never creating a cycle.
The growing tree is drawn live, edge by edge, so you watch the real cheapest connections accumulate frame by frame.
Once every point is connected, the tree holds briefly, then a fresh random point cloud and build begins.
Prim's algorithm and the cost of connecting things
A minimum spanning tree links every point in a set using the least total edge length, with no loops. The idea has a plain use: if you must wire up a group of towns or computers and want the cheapest cable, a loop is wasted because removing any edge of it leaves things still connected. The task shows up in network design, clustering and approximate solutions to harder problems.
The method here was developed by Vojtěch Jarník in 1930 and later rediscovered by Robert Prim in 1957 (and by Edsger Dijkstra in 1959), which is why it is also called Jarník's algorithm or the DJP algorithm. It builds the tree one vertex at a time from an arbitrary starting point, repeatedly adding the cheapest edge that joins the tree to a point outside it. A standard exchange argument shows this greedy choice yields a minimum spanning tree.
Kruskal's algorithm, published in 1956, reaches a minimum tree by a different route, sorting all edges and adding them from cheapest, skipping any that would form a cycle. When all edge costs are distinct the minimum tree is unique, so both end with the same one. Which edges count as cheapest depends on the distances between the random points, so every cloud builds a different tree.
A worked example
Two points sitting close together connect almost immediately, while an isolated outlier point only joins the tree once its single cheapest connecting edge is finally reached.
Settings & tips
- Accent recolours the growing tree edges.
- The point cloud and edge costs are real and randomized every run.
- A fresh point cloud generates automatically once the tree completes.
Frequently asked questions
- Is this a real minimum spanning tree algorithm?
- Yes — a real, correct Prim's algorithm implementation, run live on a randomized point cloud.
- What makes it "minimum"?
- It connects every point using the least possible total edge length of any spanning tree — a real, proven-optimal property.
- Is a key needed?
- No — it is a pure local computation.
- Is it free?
- Yes — free, no download, in your browser.
- Is the minimum spanning tree unique?
- If all edge lengths are different, yes. When ties exist, several trees can share the same minimum total.
- How does Prim's algorithm differ from Kruskal's?
- Prim's grows one tree outward from a starting point, while Kruskal's sorts all edges and merges separate fragments. Both give a minimum total.
- Why can the tree never have a cycle?
- Dropping an edge of any cycle keeps all points connected at no greater cost, so a minimum tree needs no cycle.