Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 49 ยท Network Optimization

Minimum Spanning Trees: Kruskal and Prim

Connect every node of a network at the lowest total cost: learn Kruskal's and Prim's algorithms, the cut property and union-find, with runnable Python.

A telecom company must connect six villages with fiber cable. Digging between two villages costs money, depending on distance and terrain, and the company wants every village to be reachable from every other, at the lowest total cost. It does not need a cable between all pairs, only enough cables to join everything. This is the minimum spanning tree (MST) problem, one of the cleanest problems in operations research: a simple greedy method is provably optimal.

A six-village network with the minimum spanning tree in teal, rejected cables dashed, and a list of Kruskal's decisions with total cost 16
Kruskal considers cables from cheapest to dearest and keeps each one unless it would close a loop. Five cables, total cost 16.

What you will learn

  • What a spanning tree is and why a minimum one has no cycles.
  • Kruskal's algorithm and how union-find detects cycles.
  • Prim's algorithm and how it differs.
  • Why greedy choices are optimal here (the cut property).

Key terms

Spanning tree: a set of edges that connects all nodes without forming a cycle; it always has n โˆ’ 1 edges for n nodes.

Minimum spanning tree (MST): a spanning tree of least total weight.

Cycle: a closed loop of edges. Removing one edge of a cycle never disconnects the network.

Cut: a split of the nodes into two groups; the edges between the groups cross the cut.

Union-find (disjoint sets): a data structure that tracks which nodes are already connected.

The problem

The villages are P, Q, R, S, T, U. Possible cables with their costs in thousands of dollars (example numbers) are:

Cable Pโ€“Q Pโ€“R Qโ€“R Qโ€“S Rโ€“S Rโ€“T Sโ€“T Sโ€“U Tโ€“U
Cost 4 3 5 2 6 7 4 8 3

We need a set of cables that connects all six villages with minimum total cost. Because extra cables only add cost, the best solution never contains a cycle, so it is a tree. A tree on 6 nodes has exactly 5 edges.

Kruskal's algorithm

Joseph Kruskal published this method in 1956. The idea is as greedy as it gets:

  1. Sort all edges by cost, cheapest first.
  2. Go through them in order. Add an edge if it connects two nodes that are not yet connected. Skip it if it would close a cycle.
  3. Stop when you have n โˆ’ 1 edges.

On the villages:

Order Cable Cost Decision
1 Qโ€“S 2 add
2 Pโ€“R 3 add
3 Tโ€“U 3 add
4 Pโ€“Q 4 add (joins {P, R} with {Q, S})
5 Sโ€“T 4 add (joins {P, Q, R, S} with {T, U}): now all connected
6 Qโ€“R 5 skip: Q and R are already connected through P
7 Rโ€“S 6 skip: cycle
8 Rโ€“T 7 skip: cycle
9 Sโ€“U 8 skip: cycle

The tree has the 5 edges Qโ€“S, Pโ€“R, Tโ€“U, Pโ€“Q and Sโ€“T, with total cost 2 + 3 + 3 + 4 + 4 = 16. Edges of equal cost can be taken in either order; here the final cost does not change.

Detecting cycles with union-find

How do you know whether two villages are already connected? Keep a label for each connected group. When you add an edge, merge the two groups. The union-find structure does exactly this: find(x) returns the group leader of x, and union(x, y) merges two groups. An edge closes a cycle exactly when find(u) == find(v).

Python Kruskal's algorithm with union-find

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.

Prim's algorithm

Prim's algorithm (Jarnรญk 1930, rediscovered by Prim in 1957) grows a single tree instead of many fragments:

  1. Start from any node.
  2. Repeatedly add the cheapest edge that connects a node inside the tree to a node outside it.
  3. Stop when all nodes are inside.

Starting from P: the cheapest edge leaving is Pโ€“R (3), then Pโ€“Q (4), then Qโ€“S (2), then Sโ€“T (4), then Tโ€“U (3). The tree is the same, total 16. Prim is a good choice for dense networks, Kruskal for sparse ones; with a heap both run in about m log n steps for m edges and n nodes.

Why greedy works: the cut property

Pick any cut, a split of the nodes into two groups. The cheapest edge crossing the cut belongs to some minimum spanning tree (and to every one if edge costs are all different). Why? Suppose a spanning tree T lacks that cheapest crossing edge e. Add e to T: it creates a cycle, and that cycle must cross the cut again by some other edge f that is at least as expensive as e. Swap f for e: the cost does not increase, and the result is still a spanning tree. So there is a minimum tree containing e.

Kruskal and Prim both only ever pick the cheapest edge across some cut, so every choice is safe. Together with the mirror-image cycle property (the most expensive edge of any cycle can be dropped), these facts explain why a greedy method is optimal for this problem though it fails for many others.

Checking by brute force

For a network this small we can check the claim directly: list every subset of 5 edges, keep those that form a spanning tree, and take the cheapest.

Python Check Kruskal against every spanning tree

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.

The minimum agrees with Kruskal's 16. Counting trees shows how fast the number of candidates grows, which is why we do not enumerate for big networks.

MST with scipy, and a picture

Python Compute and draw the minimum spanning tree

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.

Uses and variants

  • Network design. Cables, pipes, roads and power lines: build the cheapest connected network.
  • Clustering. Remove the most expensive k โˆ’ 1 edges of an MST to get k clusters, a method called single-linkage clustering.
  • Approximation. MST-based tours give a quick approximation for the traveling salesman problem (Chapter 8).
  • Constraints. Adding rules (such as a maximum number of links per village) makes the problem much harder than plain MST. In that case you might switch to integer programming.

MST versus shortest paths

The two problems are often confused. The MST connects all nodes at least total cost, and it ignores where traffic flows. A shortest-path tree from S minimizes the distance from S to every node, which can cost more in total. In the village network, the cheapest route from U to R is U โ†’ T โ†’ R (cost 3 + 7 = 10), which uses the cable Rโ€“T of cost 7 that the MST rejects. The shortest-path tree from U therefore costs more in total (19 or 20, depending on how a tie for P is broken) than the minimum spanning tree (16). Use the MST when you pay for edges once; use shortest paths when you pay for traveling.

Common misconceptions

"The MST gives the shortest route between any two nodes." It minimizes total edge cost, not individual distances.

"A spanning tree must contain the cheapest edge." The cheapest edge is safe in Kruskal's method, but spanning trees in general need not contain it; a minimum one does (when costs are distinct).

"Greedy always works." It does here because of the cut property. For other problems, such as the knapsack problem, greedy can fail.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many edges does a spanning tree on 6 nodes have?

    A tree on n nodes has exactly n โˆ’ 1 edges.
  2. 2. In Kruskal's algorithm, when is an edge skipped?

    An edge inside a connected group would form a cycle and add cost without connecting anything new.
  3. 3. What is the total cost of the minimum spanning tree of the village network?

    The tree Qโ€“S, Pโ€“R, Tโ€“U, Pโ€“Q, Sโ€“T costs 2 + 3 + 3 + 4 + 4 = 16.
  4. 4. What does Prim's algorithm do at each step?

    Prim grows one tree by always adding the cheapest edge that leaves it.
  5. 5. The cut property says that the cheapest edge across any cut...

    That is why greedy choices in Kruskal and Prim are safe.

Summary

  • A minimum spanning tree connects all nodes with n โˆ’ 1 edges at least total cost.
  • Kruskal sorts edges and skips those that would create a cycle (union-find detects them); Prim grows one tree from a start node.
  • Both are greedy and optimal because of the cut property.
  • The village network has MST cost 16 using Qโ€“S, Pโ€“R, Tโ€“U, Pโ€“Q and Sโ€“T.
  • MST minimizes total edge cost; it does not give shortest routes.

Next: Maximum Flow and Minimum Cut