minimum spanning tree

The spanning tree of a weighted, connected graph whose edges have the smallest possible total weight.

In more detail

It answers "what is the cheapest way to connect everything?", as when laying cable between data centres. Kruskal's and Prim's algorithms both build one greedily, and both are justified by the cut property. It always has exactly V minus one edges.

Related terms

Taught in

References