Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 36 · Trees and Spanning Trees

Minimum Spanning Trees

Find the cheapest way to connect a weighted graph: spanning trees, the cut and cycle properties, Kruskal's algorithm with union-find and Prim's algorithm with a heap, checked in Python.

A company wants to lay cable between six offices. Every possible link has a price. What is the cheapest set of links that still connects all offices? Nobody needs two routes between the same pair, so the answer contains no cycle: it is a tree. A spanning tree of a connected graph G is a subgraph that includes every vertex and is a tree, so it has exactly n - 1 edges. If edges have weights, a minimum spanning tree (MST) is a spanning tree of smallest total weight.

graph LR
  A -- 7 --- B
  A -- 5 --- D
  B -- 8 --- C
  B -- 9 --- D
  B -- 7 --- E
  C -- 5 --- E
  D -- 15 --- E
  D -- 6 --- F
  E -- 8 --- F
  E -- 9 --- G
  F -- 11 --- G

Seven vertices; the MST uses six of these eleven edges.

Two properties that make it easy

  • Cut property. Split the vertices into two groups. The cheapest edge crossing between the groups belongs to some MST (to every MST if it is the unique cheapest). So we can always safely pick it.
  • Cycle property. The heaviest edge on any cycle (if unique) belongs to no MST: swapping it for another cycle edge gives a cheaper tree.

Both greedy algorithms below are direct applications of these facts. Greedy works here, unlike on many graph problems.

Kruskal's algorithm

Sort all edges by weight. Walk through them from cheapest to heaviest, and keep an edge if it connects two different components, i.e. does not close a cycle. Stop at n - 1 edges. Cycle checks use union-find.

Python Kruskal's algorithm

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sorting dominates, so Kruskal runs in O(m log m).

Prim's algorithm

Prim grows one tree from a start vertex. At each step add the cheapest edge connecting the tree to a vertex outside it. A min-heap holds candidate edges. This looks a lot like Dijkstra, but the key is the edge weight alone, not the distance from the source.

Python Prim's algorithm with a heap

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With a binary heap Prim runs in O(m log n). Both algorithms find a tree of the same total weight (39 for this graph), though the edge sets may differ when weights tie.

Compare both with networkx

Python Kruskal, Prim and networkx agree

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three agree on the weight. If all edge weights are distinct, the MST is also unique, which is a handy sanity check.

Which one to use

Kruskal Prim
Idea Add cheapest edge that makes no cycle Grow one tree from a start vertex
Works on An edge list An adjacency list
Time O(m log m) O(m log n) with a heap
Best for Sparse graphs Dense graphs (array version O(n²))

Applications include network and road design, clustering (cut the heaviest k - 1 MST edges to get k clusters), image segmentation and approximating the traveling salesman problem.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. How many edges does a spanning tree of a connected graph with 15 vertices have?

    Any spanning tree has n - 1 = 14 edges.
  2. 2. Kruskal's algorithm rejects an edge when it:

    Such an edge would close a cycle, so it cannot be part of a tree.
  3. 3. What data structure makes Kruskal's cycle check fast?

    Union-find tells in near constant time whether two vertices are already connected.
  4. 4. If all edge weights are distinct, the minimum spanning tree is:

    Distinct weights remove ties, so the cut and cycle properties pick one tree.

Summary

  • A spanning tree connects all vertices with n - 1 edges; an MST minimizes the total weight.
  • The cut property (cheapest crossing edge is safe) justifies greedy algorithms.
  • Kruskal sorts edges and uses union-find; Prim grows a tree with a heap.
  • Both run in about O(m log n) and produce trees of equal weight.
  • With distinct weights the MST is unique.

Next: Prüfer Codes and Cayley's Formula