Computer Science · Lesson 15
Minimum Spanning Tree
How do you connect ten cities with roads, cables, or pipes using the least total material? That's the minimum spanning tree problem — a classic in graph theory that has routed internet cables, power grids, airline networks, and water systems across the world.
Kruskal and Prim — Two Paths to the Same Answer
In 1956, mathematician Joseph Kruskal published an elegant greedy algorithm: sort all edges in a graph by weight, then keep adding the cheapest edge that doesn't create a cycle — until every node is connected. One year later in 1957, computer scientist Robert Prim independently found a different approach: start from any node, and repeatedly add the cheapest edge that connects the current tree to a node not yet in it. Both algorithms always produce the same optimal result — the minimum spanning tree — and both are provably correct. Their work appears in network design, biology, image segmentation, and cluster analysis to this day.
Graphs, Spanning Trees, and Minimality
Spanning tree — a subgraph that connects all nodes with no cycles (uses exactly n−1 edges)
Minimum spanning tree — the spanning tree with the smallest possible total edge weight
Cycle — a path that starts and ends at the same node (adding one creates redundancy)
Kruskal's Algorithm — Step by Step
- 1List all edges in the graph sorted by weight, cheapest first.
- 2Consider each edge in order. Ask: would adding this edge create a cycle?
- 3If no cycle — add it to the MST (shown in green).
- 4If it would create a cycle — reject it (shown in red).
- 5Stop when n−1 edges have been added. All nodes are now connected.
Prim's Algorithm — Step by Step
- 1Start with a single node as the whole "tree so far."
- 2Look at every edge that connects a node already in the tree to a node that isn't.
- 3Add the cheapest of those crossing edges to the tree (shown in green), pulling in one new node.
- 4Edges that now sit entirely inside the tree are no longer useful — they're marked rejected (shown in red).
- 5Repeat until every node has joined the tree.
Both are greedy algorithms — they always make the locally cheapest choice available. Kruskal's thinks in terms of the whole edge list at once; Prim's grows outward one connected blob at a time, like a snowball rolling through the graph. Remarkably, both strategies are provably globally optimal — try both below and you'll always end up with the same total cost.
MST Visualiser
Click Step to add one edge at a time, or Run All to complete instantly. Green edges are in the MST; red edges were rejected (would create a cycle); grey edges have not yet been considered.
Real-World Applications
Practice Problems
Easy1. A spanning tree for a graph with n nodes has exactly how many edges?
Easy2. Kruskal's algorithm considers edges in what order?
Medium3. A graph has 5 nodes and edges with weights 2, 3, 4, 5, 6, and 7. The MST needs 4 edges. What is the minimum possible MST total weight?
Medium4. What property makes a path a "cycle" in graph theory?
Challenge5. Prim's algorithm grows the MST by always adding the cheapest edge connecting the current tree to a new node. For a graph with n = 6 nodes, how many steps (edge additions) does Prim's take to complete the MST?
Worked Example: Kruskal's Greedy Edge Selection & Cycle Rejection
Trace Kruskal's algorithm on a 5-node network to understand how greedy edge selection and Disjoint-Set union-find produce a globally optimal spanning tree.
Problem: Connect 5 Cities {A, B, C, D, E} with Minimum Fiber Optic Cable
We are given an undirected graph with 5 vertices (\(V = 5\)) and 7 candidate cable links. A valid spanning tree requires exactly \(V - 1 = 4\) edges with no cycles. The candidate links with their installation costs are:
(A-B: 2), (B-C: 3), (A-C: 4), (C-D: 5), (B-D: 6), (D-E: 7), (C-E: 8)
- Step 1: Sort All Edges in Ascending Order of Cost.
Kruskal's algorithm begins with every node in its own disjoint set: {A}, {B}, {C}, {D}, {E}. Sorted list: (A-B: 2), (B-C: 3), (A-C: 4), (C-D: 5), (B-D: 6), (D-E: 7), (C-E: 8). - Step 2: Inspect (A-B: 2) and (B-C: 3).
Edge (A-B: 2) connects set {A} with set {B}. Because they belong to different components, we accept (A-B). Component: {A, B}.
Edge (B-C: 3) connects set {A, B} with set {C}. Because C is in a different set, we accept (B-C). Component: {A, B, C}. Total edges added = 2. - Step 3: Inspect (A-C: 4) — Cycle Detection in Action!
Edge (A-C: 4) connects node A and node C. When the algorithm runsfind(A)andfind(C), both return the same representative root {A, B, C}. Because A and C are already connected through B, adding (A-C) would form a closed cycle (A-B-C-A). Therefore, the algorithm rejects edge (A-C), which means no redundant cable is installed. - Step 4: Inspect (C-D: 5) and (D-E: 7).
Edge (C-D: 5) merges {A, B, C} with {D}. Accepted! Edges added = 3.
Edge (B-D: 6) connects nodes already in the same component {A, B, C, D}. Cycle detected; rejected!
Edge (D-E: 7) merges {A, B, C, D} with {E}. Accepted! Edges added = 4. - Termination: Because exactly \(V - 1 = 4\) edges have been added, the algorithm halts immediately without inspecting (C-E: 8).
Total MST Weight: \(2 + 3 + 5 + 7 = 17\). The Cut Property of minimum spanning trees guarantees this greedy result is mathematically optimal.
Self-Check Question
If a connected graph has 10 routers and 25 possible links, how many links will its Minimum Spanning Tree contain, and what happens if you add one more link to the completed MST?
Show Answer & Proof
Answer: The MST will always contain exactly \(V - 1 = 10 - 1 = 9\) links. If any additional link is added to an existing spanning tree, it will inevitably create exactly one cycle, because a tree provides a unique simple path between every pair of vertices. Therefore, introducing a second path between any two vertices closes a loop.
Sources & Further Reading
Seminal papers in greedy optimization, graph algorithms, and network design.
- Kruskal, Joseph B. “On the shortest spanning subtree of a graph and the traveling salesman problem.” Proceedings of the American Mathematical Society, 7(1), 48–50 (1956). doi:10.1090/S0002-9939-1956-0078686-7.
- Prim, Robert C. “Shortest connection networks and some generalizations.” Bell System Technical Journal, 36(6), 1389–1401 (1957). doi:10.1002/j.1538-7305.1957.tb01515.x.
- Borůvka, Otakar. “O jistém problému minimálním” (On a certain minimal problem). Práce Moravské Přírodovědecké Společnosti, 3, 37–58 (1926). The earliest known MST algorithm, designed for rural electrification networks in Moravia.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms (4th ed.). MIT Press (2022). Chapter 21: Minimum Spanning Trees.