Mr. Scandrett's ClassroomOS

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.

This is a greedy algorithm — it always makes the locally cheapest choice at each step. Remarkably, this greedy strategy is provably globally optimal for spanning trees.

Kruskal's Algorithm 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.

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.