Computer Science · Lesson 15

Minimum Spanning Tree

Graph Theory Kruskal's Prim's Greedy Algorithms Networks

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

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.

Total Cost—
Edges Added0
Considered0
Added to MST Rejected (cycle) Not yet considered Currently examining

Real-World Applications

🌍
Internet Backbone Routing Laying undersea fibre-optic cables between continents is enormously expensive. Network engineers use MST algorithms to find the minimum-cost topology that keeps all nodes connected.
⚡
Power Grid Design Electrical utilities use MST algorithms to plan transmission lines connecting substations and cities with the minimum total cable length, reducing construction and transmission-loss costs.
💧
Water & Gas Pipelines Municipal planners connect neighbourhoods to water or gas networks using MST-derived layouts to minimise pipe length, excavation costs, and ongoing maintenance.
🧠
Machine Learning Clustering In single-linkage hierarchical clustering, the MST of a dataset's similarity graph defines which data points are most closely related — used in genomics, image segmentation, and market analysis.
Crew testing cable aboard the CS Faraday while laying a trans-Tasman submarine cable
Laying a real backbone cableEvery metre of undersea cable is expensive to lay, so planners look for a minimum-cost network — exactly the problem an MST solves. State Library of New South Wales collection · no known restrictions · Wikimedia Commons
Row of high-voltage electricity transmission towers at sunset
Connecting a grid for the least steelUtilities route transmission towers between substations to minimise total line length — an MST on a map of possible tower sites. Matthew T Rader · CC BY-SA 4.0 · Wikimedia Commons

Practice Problems

Easy1. A spanning tree for a graph with n nodes has exactly how many edges?

Hint: A tree with n nodes always has exactly n−1 edges — one fewer than the number of nodes. Adding any edge would create a cycle.

Easy2. Kruskal's algorithm considers edges in what order?

Hint: Kruskal's is a greedy algorithm — it always picks the cheapest available edge that doesn't create a cycle.

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?

Hint: Kruskal's picks the 4 cheapest edges (assuming no cycles): 2 + 3 + 4 + 5 = 14.

Medium4. What property makes a path a "cycle" in graph theory?

Hint: A cycle is a closed path — you can follow edges and return to the starting node, meaning at least one node is visited more than once.

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?

Hint: Any spanning tree on n nodes has n−1 edges. Prim's adds exactly one edge per step, so it always takes n−1 = 5 steps for n = 6.

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)

  1. 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).
  2. 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.
  3. Step 3: Inspect (A-C: 4) — Cycle Detection in Action!
    Edge (A-C: 4) connects node A and node C. When the algorithm runs find(A) and find(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.
  4. 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.
  5. 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.