Learn · Spanning Trees
Connect every junction with the least street.
Lay fibre to every crossroads of a neighbourhood, or plan the shortest snow-plough network – that is a minimum spanning tree. This lab builds one on the real streets of a generated city, one edge at a time.
How it works
One edge at a time
-
Pick a situation
Fibre for a neighbourhood, new water mains, a snow-plough network – each a real question on real streets, with junctions lettered A, B, C …
-
Pick an algorithm
Kruskal sorts every street by length, Jarník (Prim) grows one tree from a start, Borůvka grows many at once, Edmonds handles one-way streets.
-
Step through it
Watch each street get accepted or rejected. The inspector shows the union–find sets, the priority queue and the line of pseudocode running.
-
Change the city
Close a street and the tree is recomputed. Switch between the 3D city and a 2D map, and grow the lab from a small block to the whole city.
What you learn
Three greedy algorithms, one answer
Kruskal, Jarník and Borůvka look nothing alike while they run, yet they always end with a tree of the same total length – because each only ever adds the cheapest street that crosses some cut. Seeing all three on the same streets makes that cut property click.
When the streets are one-way, an ordinary spanning tree is not enough: you need every junction reachable from a root. That is a minimum arborescence, and the lab shows Edmonds' algorithm contracting cycles to find it.
Spanning Trees at a glance
- Algorithms
- Kruskal, Jarník (Prim), Borůvka, Edmonds
- Shows
- Union–find, priority queue, pseudocode, edge weights in metres
- Views
- 3D city or 2D map, small block to whole city
Keep exploring
More to try
-
Learn
Pathfinding Visualizer
Explore how classic graph algorithms navigate a real Procedity city.
-
Learn
Maximum Flow
How many cars an hour get across town? Watch Ford–Fulkerson, Edmonds–Karp, Dinic and MPM fill the streets.
-
Learn
Minimum Cut
Where is the street network weakest? Stoer–Wagner, Karger and the Gomory–Hu tree split a real city.
-
Game
Find the car
One car in town has a colour no other car has. Spot it in traffic as fast as you can.