AlgoScope

Minimum Spanning Tree

The cheapest set of V - 1 edges that still leaves every vertex reachable, and the three ways of choosing them.

3 topics1 lessons1 families

A spanning tree of a connected graph on V vertices is any set of V - 1 edges that keeps the whole graph in one piece. A minimum spanning tree is the one whose weights add up to the least. Laying cable, wiring a network and clustering points by nearest neighbour are all this question with different words.

All three algorithms rest on the same fact, the cut property: split the vertices into two groups however you like, and the lightest edge crossing the split belongs to some minimum spanning tree. Prim treats the tree built so far as one side and repeatedly takes the cheapest edge leaving it, using a priority queue, O(E log V). Kruskal makes the cut differently: sort every edge and accept each one whose ends are in different components, which is exactly the question union-find answers, O(E log E). Boruvka lets every component choose its own cheapest outgoing edge at the same time, so the number of components at least halves each round.

The cost is the sort or the heap, not the walk over the graph. Note what the result does not give you: a minimum spanning tree is not a shortest path tree, and the route it offers between two vertices can be far longer than the shortest path in the original graph.

After this you can

  • State the cut property and use it to justify accepting one particular edge
  • Run Kruskal with union-find and say why the cycle check is a find rather than a search
  • Pick Prim on a dense graph and Kruskal on a sparse edge list, and say what decided it
  • Explain why a minimum spanning tree is not a shortest path tree
431242650✓12345

Edges leaving the tree: 0-2 (3), 0-1 (4). The cheapest is 0-2 at 3, so 2 joins the tree. Total 3.

Open in the player →or start at step 2

In this order

  1. PrimGrow one tree from a start vertex, always adding the cheapest edge that leaves it.
  2. KruskalSort the edges by weight and take each one that joins two different components, which union-find answers.
  3. BoruvkaEvery component picks its cheapest outgoing edge simultaneously; components halve each round.

Where people go wrong

Ties mean there is no single answer

When two edges have equal weight there can be several minimum spanning trees, all with the same total. A test that asserts on one particular edge set is checking your tie-break, not the algorithm. Only distinct weights give a unique tree.

Kruskal without union by size and path compression

A find that walks a long chain is O(n), and unions that always hang the first root under the second build exactly that chain. With union by size and path compression the pair is near constant and the sort dominates; without them Kruskal can slow to quadratic.

Input that is not connected

A disconnected graph has no spanning tree at all. Kruskal happily ends with a forest, one tree per component, and the total it reports is meaningless as an MST. Count the accepted edges and check for V - 1 before using the number.

Or a different category

Shortest Path

You want the cheapest route between two specific vertices rather than the cheapest way to connect all of them.

Greedy

You want the general argument for when taking the locally cheapest option is safe, rather than this one application of it.

Lessons that teach these