Minimum Spanning Tree

Connect all nodes at the lowest total edge weight with Kruskal (sort edges, join with DSU) or Prim (grow one tree with a heap), and know why greedy works.

40 minCF 1600–20004 interactive9 problems

The problem

A spanning tree of a connected graph is a set of edges that links all $n$ nodes with no cycle. Every spanning tree has exactly $n - 1$ edges. A minimum spanning tree (MST) is the spanning tree with the smallest total weight.

Real shapes of the same question: lay cable to connect all offices as cheaply as possible, rebuild the cheapest set of roads so every city is reachable, cluster points by repeatedly joining the closest ones.

If the graph is not connected there is no spanning tree. You get a spanning forest, one tree per component.

1 of 8