Minimum spanning trees

A minimum spanning tree is the cheapest set of edges that connects every node in a weighted graph without forming any loops. Picture wiring a group of towns together with the least total cable: you don’t care about the route between any two towns, only that everything is connected and the total is as small as possible. The key fact is that the cheapest edge crossing any division of the nodes into two groups is always safe to include. Kruskal’s algorithm uses this by adding edges from cheapest to most expensive and skipping any that would form a loop; Prim’s grows a single tree outward, always adding the cheapest edge that reaches a new node.