Computer Science / Unit 3 CS 0152 short lesson, about 20 seconds
The Minimum Spanning Tree
Captions available
The idea
The minimum spanning tree problem asks for the lowest-cost way to connect all of a graph's vertices — a problem where a crafted greedy rule provably finds the optimum.
In practice
Wiring a whole town to broadband at least cost is this problem in work clothes.
Where people slip
The proof, not the greed, makes it safe.
Your place on the trail
Every lesson rests on earlier ones and opens later ones. Tap any to jump.
Builds on
Unlocks
Something wrong in this lesson? Flag it · Sources for Computer Science