Explain like I'm five · Systems

What is a Minimum Spanning Tree (MST)?

Minimum spanning trees, told as a story about piping every garage branch together for the lowest total cost, with no loops.

ABCDE7463589all five branches must be piped togetherso many possible pipe routes, each a different cost

All five branches must be piped together.So many possible pipe routes, each a different cost.

ABCDE7463589piping every path connects everything, but costs far too muchwe want only the needed pipes to save money

Laying every possible pipe connects everything, but costs far too much.We want only the needed pipes to save money.

ABCDE4635789MST: connect every branch for the lowest total cost, with no loopsjust four green pipes (3+4+5+6) connect all five branches

An MST connects every branch for the lowest total pipe cost, with no loops.Just four green pipes connect all five branches.

Cheapest firstlooks at the lowest-cost pipe first
No cycles allowedskips a pipe that would just loop back
Grow the networkextends the connected set step by step
Connect all five branchesall five branches end up connected
Kruskal — pick cheapest firstline up every pipe by costkeep picking as long as no loop formschooses by looking at every pipe at oncePrim — grow from one branchstarts from a single branchadds the cheapest pipe leaving the networkgrows the connected network step by step

There are two main ways to pick the pipes: Kruskal and Prim.Kruskal chooses by looking at every pipe; Prim grows the network from one branch.

AB3pick the cheapest pipe, but skip it if both ends already connectCDE2without the no-loop rule, pipes loop and waste moneyboth 'cheapest' and 'no loop' must hold for a true MST

Chasing only the cheapest path can create a cycle.Both 'cheapest' and 'no loop' must hold for a true MST.

In one breath

A minimum spanning tree (MST) connects every point for the lowest total edge cost, with no cycles, so all points stay linked.

A minimum spanning tree is a subgraph of a weighted graph that connects every vertex, has no cycles, and minimizes the total edge weight. Kruskal's algorithm sorts all edges by weight and repeatedly adds the cheapest one that doesn't create a cycle (checked via union-find). Prim's algorithm starts from one vertex and repeatedly adds the cheapest edge connecting the growing tree to the outside, growing the tree one edge at a time. Both produce a tree with n-1 edges for n vertices.

When grown-ups say it

Minimum Spanning Tree
The network that connects every branch for the lowest total pipe cost. n vertices means n-1 edges.
Kruskal's Algorithm
The method of picking cheap pipes in order. Sorts all edges up front, then picks.
Prim's Algorithm
The method of growing outward from one branch. Extends only via the cheapest edge from what's connected.
Cycle
Pipes looping back to reconnect the same branches. Must never occur in an MST.
Weighted Graph
The map with a cost written on every pipe. An MST minimizes the sum of these costs.
Union-Find
The tool that quickly checks if two branches are already connected. Used by Kruskal to check for cycles.
Greedy Algorithm
The strategy of always picking the cheapest option right now. Both Kruskal and Prim follow this strategy.
Shortest Path Algorithm
Finding the single cheapest route between two specific points. A different problem — MST's goal is connecting everyone, not one pair.
Next story
The Parts-Warehouse Manager Who Never Overwrites →
Want another term as a picture book? Request →