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
- spanning tree — A subset of a connected graph's edges that links all V vertices together with no cycles, using exactly V minus one edges.
- Kruskal's algorithm — An algorithm that builds a minimum spanning tree by sorting all edges by weight and adding each one unless it would create a cycle.
- Prim's algorithm — An algorithm that builds a minimum spanning tree by growing it from one start vertex, always adding the cheapest edge leading out of the tree.
- cut property — The fact that, for any way of splitting a graph's vertices into two groups, the cheapest edge crossing between the groups belongs to some minimum spanning tree.
Taught in
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers