If you noticed from the last topic, spanning trees are just like normal trees except for maybe

• their lack of leaves.
• their lack of bark.
• only kind-of tenuously looking like trees if you flip them upside-down and then squint at them from the corner of your eye.

Spanning trees are about as treelike as normal trees. In fact, they're the exact same thing.

[pause for dramatic effect]

The only difference between a normal tree and a spanning tree is that a spanning tree comes from an already-existing graph. In fact, all they do is find a path to every node in a tree without making

• any loops.
• any cycles.
• multiple paths between any two nodes.

If a graph can't be completely connected, one spanning tree won't cut it. Instead, we'll need a spanning forest, where you use multiple trees to represent a path through the graph.

Why do we need spanning trees at all? They're going to help us walk through graphs. That way, when we need to methodically walk through paths to figure something out, we'll have a way to keep track of where we've been without walking in circles.

Better yet, if we have weighting on a tree, where every edge has a weight attached to it, we can find the minimum spanning tree, which will give us the lowest cost for going through the graph. It's pretty great.

Now if only there was a graph theory tree we could actually hug…