Minimum spanning trees are all about finding the shortest paths between things in a weighted graph. You want to:

• Touch every vertex
• Have the smallest total weight between then.

You end up without cycles, as it'd be more expensive to make one. The trick is always picking a "safe" edge to add on every turn.

Two major algorithms:

Kruskal's Algorithm:

Put all the weights in order - iterate through, adding the lightest edge that doesn't great a cycle at a time

Prim's Algorithm:

1. Pick a vertex!
2. Greedy algorithm it!
3. That's it (don't make cycles)