Minimum Spanning Trees

Algorithms for connecting all vertices in a weighted graph using the minimum total edge weight. Despite being one of the oldest problems in computer science, MST algorithms remain a cornerstone of network design, clustering, and approximation algorithms, with surprising recent theoretical advances.

Introductory to Advanced

• Basic algorithms (Kruskal, Prim): Introductory/Intermediate
• Correctness proofs (cut/cycle properties): Intermediate
• Analysis and data structures (Union-Find): Intermediate
• Advanced algorithms (Borůvka, Karger-Klein-Tarjan): Advanced
• Verification algorithms: Advanced

The skill that connects everything: MST isn’t just about finding cheap networks—it’s about understanding greedy algorithms, data structure design, and the surprising depth hidden in simple problems. The mental model applies to:

• Network design (connecting cities, laying fiber optic cables)
• Clustering algorithms (single-linkage clustering is MST-based)
• Approximation algorithms (MST gives 2-approximation for metric TSP)
• Understanding when greedy works (matroid theory)

War Story - The Airplane Toll Problem: In the 1990s, a major airline wanted to optimize their hub-and-spoke network. They needed to connect 100 cities with minimum total flight distance. A naive approach would require checking exponentially many spanning trees. MST algorithms solved this in seconds, saving the airline millions in reduced route mileage. The insight: network design is everywhere, and MST provides optimal solutions when you need minimal-cost connectivity.

War Story - Image Segmentation via Clustering: In 1998, Felzenszwalb and Huttenlocher revolutionized image segmentation using MST-based clustering. Build a graph where pixels are nodes and edge weights measure color/texture dissimilarity. The MST reveals natural boundaries—breaking edges in order of decreasing weight creates a hierarchical segmentation. This algorithm processes high-resolution images in near-linear time and remains competitive with modern ML approaches for certain applications.

1. Kruskal’s Algorithm - Sort edges, add if doesn’t create cycle (Union-Find)
2. Prim’s Algorithm - Grow tree from arbitrary vertex (priority queue)
3. Borůvka’s Algorithm - Parallel-friendly: all vertices find cheapest outgoing edge simultaneously

4. Karger-Klein-Tarjan Randomized Algorithm - O(m) expected time, theoretical breakthrough
5. MST Verification - Testing if a given tree is MST faster than computing MST
6. Dynamic MST - Maintaining MST under edge insertions/deletions
7. Euclidean MST - Special algorithms for points in R^d

• Required:

  • Basic graph theory (trees, cycles, cuts)
  • Proof by induction/exchange arguments
  • Priority queues or Union-Find data structures

• Helpful:

  • Understanding of greedy algorithms
  • Matroid theory (for deeper understanding of why greedy works)
  • Amortized analysis (for Union-Find)

Setup: You’re building a cable network to connect 10 cities. Each pair of cities has a cost to lay cable. You need to ensure every city can reach every other city (possibly through intermediate cities), while minimizing total cable cost.

Naive approach: There are exponentially many spanning trees. Trying them all is impossible for even modest-sized networks.

Student exploration:

• What if we always pick the cheapest available cable that connects a new city?
• What if we always pick the globally cheapest cable that doesn’t create a loop?

The insight: Both strategies (Prim and Kruskal) work! The exchange argument shows any deviation from these greedy choices can be improved.

Generalization: This teaches that greedy algorithms need correctness proofs, not just intuition. The cut property and cycle property formalize why these greedy choices are safe.

Setup: Suppose you’ve connected some cities already (a forest). You look at cities in one component versus all others. What can you say about the cheapest edge crossing this boundary?

Student discovery: That cheapest crossing edge must be in some MST! Why? If your supposed MST doesn’t include it, you could remove a heavier crossing edge and add this cheaper one, getting a lighter spanning tree.

The revelation: This “exchange argument” is the proof technique in combinatorial optimization. You see it everywhere: matching theory, matroid optimization, scheduling algorithms.

Setup: In Kruskal’s algorithm, we need to quickly check: “Does adding this edge create a cycle?” How do we do this efficiently for thousands of edges?

Naive approach: Run DFS to check if endpoints are already connected. Takes O(V) per edge.

Union-Find insight: Maintain connected components with find (which component is this vertex in?) and union (merge two components). With path compression and union by rank, operations take nearly O(1) amortized time.

The insight: Data structures aren’t just about storing data—they’re about making the right operations cheap. Union-Find enables efficient Kruskal’s algorithm.

Greedy strategies in decision-making: MST algorithms teach us when greedy strategies are optimal. In life, we often face decisions: should we choose the best local option now, or consider global consequences? MST provides a rare example where local optimization yields global optimality—but only under specific conditions (the cut property).

Understanding when greedy works (and when it fails) transfers to:

• Career decisions: when to take the best immediate opportunity vs. planning long-term
• Project management: when to tackle the easiest/quickest tasks vs. strategic sequencing
• Resource allocation: when marginal cost drives optimal decisions

Hierarchical clustering as understanding: The MST-based clustering approach mirrors how humans naturally categorize. Start with individual items, gradually group similar ones. The dendrogram (tree showing merging order) reveals multi-scale structure—fine-grained distinctions at bottom, coarse groupings at top. This appears in biological taxonomy, organizational hierarchies, and concept learning.

Statement: For any cut (S, V-S) of the graph, the minimum-weight edge crossing the cut is in some MST.

Why it matters: This justifies all greedy MST algorithms. Prim and Kruskal repeatedly apply the cut property with different cuts.

Statement: For any cycle, the maximum-weight edge in the cycle is not in any MST (unless multiple edges tie for maximum).

Why it matters: Provides a deletion rule (dual to cut property’s insertion rule) and justifies reverse-delete algorithms.

Statement: If all edge weights are distinct, the MST is unique.

Proof insight: Exchange arguments show if two MSTs differ, they can’t both be minimum.

MSTs are a special case of matroid optimization. Matroids are structures where greedy algorithms work. Understanding this abstraction reveals why greedy succeeds for MST but fails for other problems (e.g., TSP).

• Kleinberg & Tardos §4.5-4.6 - Excellent motivation, clear proofs of cut/cycle properties
• Skiena §6.1 - Practical perspective, war stories of network design
• Erickson Chapter 7 - Emphasizes proof techniques and exchange arguments
• CLRS Ch 23 - Comprehensive coverage including advanced algorithms
• DPV §5.1 - Concise treatment with matroid connections

• CMU 15-850 - Includes Karger-Klein-Tarjan randomized algorithm
• Stanford CS261 - Connects MST to matroid theory and LP duality
• MIT 6.046J - Standard treatment with Union-Find analysis

• Karger, Klein, Tarjan (1995) - “A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees” (breakthrough theoretical result)
• Pettie, Ramachandran (2002) - “An Optimal MST Algorithm” (optimal but not practical)
• Chazelle (2000) - “A minimum spanning tree algorithm with inverse-Ackermann type complexity” (near-linear deterministic)

• Union-Find Data Structure: Kruskal’s algorithm motivates amortized analysis and path compression
• Greedy Algorithms: MST is the canonical example where greedy is optimal
• Matroid Theory: MST problem is graphic matroid optimization
• Approximation Algorithms: MST gives 2-approximation for metric TSP
• Clustering: Single-linkage hierarchical clustering = MST edge deletion sequence
• Network Design: MST lower bounds more complex survivable network design problems
• Parallel Algorithms: Borůvka’s algorithm naturally parallelizes

1. MST Algorithm Race

   • Implement Kruskal, Prim (binary heap, Fibonacci heap), Borůvka
   • Benchmark on random graphs, grid graphs, complete graphs
   • Analyze when each performs best
   • Visualize algorithm progress (edge additions)
   • Study practical performance vs. theoretical bounds

2. Image Segmentation via MST

   • Implement Felzenszwalb-Huttenlocher algorithm
   • Build pixel similarity graph from image
   • Compute MST, remove edges by decreasing weight
   • Compare segmentation quality at different scales
   • Apply to medical imaging (tumor detection) or satellite imagery

3. Network Design Optimizer

   • Tool for designing low-cost infrastructure networks
   • Input: locations (cities) and pairwise costs (distance)
   • Compute MST for minimal connectivity
   • Add constraints: bounded degree, redundancy (2-edge-connected)
   • Visualize solutions on geographic maps

4. Union-Find Performance Explorer

   • Implement Union-Find with/without path compression, union by rank
   • Measure performance on different operation sequences
   • Visualize tree structures showing path compression effects
   • Demonstrate amortized analysis empirically
   • Compare theoretical α(n) to actual operation counts

5. Hierarchical Clustering Tool

   • Implement MST-based single-linkage clustering
   • Input: high-dimensional data points
   • Build similarity graph (k-nearest neighbors)
   • Compute MST and create dendrogram
   • Interactive visualization showing clusters at different thresholds
   • Compare to k-means, DBSCAN

1-3 lectures depending on depth

• 1 lecture: Kruskal and Prim algorithms, cut property, basic correctness
• 2 lectures: + Union-Find analysis, Borůvka, applications (clustering, approximation)
• 3 lectures: + Advanced topics (Karger-Klein-Tarjan, MST verification, Euclidean MST)

1. “MST finds the shortest path between all pairs of vertices”

   • False! MST minimizes total edge weight, not pairwise distances. Shortest paths ≠ MST.

2. “Prim’s algorithm starts from a specific vertex, so the MST depends on which vertex you choose”

   • False! The MST is determined by edge weights (and is unique if weights are distinct). Starting vertex doesn’t matter.

3. “Kruskal’s algorithm requires sorting, so it’s always O(m log m)”

   • Partially false. If edges are already sorted or bounded weights, you can avoid sorting overhead.

4. “MST is always unique”

   • False! Only if all edge weights are distinct. With ties, multiple MSTs can exist.

5. “Greedy algorithms work for MST, so they work for similar problems like TSP”

   • False! This overgeneralization is dangerous. MST has matroid structure enabling greedy optimality. TSP does not.

Traditional (banking model):

“A spanning tree is a connected acyclic subgraph containing all vertices. Here’s Kruskal’s algorithm: sort edges, add if no cycle. Here’s the proof via cut property. Memorize this.”

Problem-posing approach:

“You need to build a cable network connecting cities as cheaply as possible. What strategies make sense? If you’ve connected some cities, which cable should you add next? Why does choosing the cheapest option work here when greedy fails for other problems? Let’s discover the structure that makes this work…”

The difference: Students construct the algorithms through guided exploration rather than receiving them as finished products. They develop intuition for exchange arguments and greedy correctness that transfers to other problems.

Curriculum placement:

• Week 3-4 for graduate courses (after basic graph algorithms, example of greedy)
• Early-to-mid for advanced undergraduate courses

Prerequisites check: Students need basic graph theory (what’s a tree, what’s a cycle) and ideally have seen one greedy algorithm before (e.g., interval scheduling).

Why early:

• MST is approachable—problem is intuitive, algorithms are simple, yet proofs are deep
• Sets up greedy algorithms and matroid theory
• Motivates advanced data structures (Union-Find, Fibonacci heaps)
• Provides a “success story” early in the course to build confidence

Relationship to other topics:

• After: Basic graph traversal (BFS/DFS) and elementary greedy examples
• Before: More complex greedy algorithms, matroid theory, approximation algorithms
• Parallel: Can be taught alongside Union-Find for data structures unit

Ready for students? ✓ Yes - simple to state, algorithms are intuitive, yet rich in proof techniques and applications from networking to clustering.