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.

Spanning Trees on a procedurally generated 3D city (seed 2024)
Free · in your browser AlgorithmsKruskalJarníkBorůvkaInteractive

One edge at a time

  1. 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 …

  2. 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.

  3. 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.

  4. 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.

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