Algorithms

Minimum Spanning Trees

June 10, 2026 at 07:19 AM
22 min reading
4 views

A spanning tree connects all vertices with exactly V-1 edges and no cycles. A Minimum Spanning Tree (MST) does this with minimum total edge weight. MST algorithms solve practical problems: network design, clustering, approximation algorithms, and more. This article covers Union-Find (the key data structure), Kruskal's greedy edge selection, Prim's greedy vertex growth, and their applications.

πŸ“‹ At a Glance

AlgorithmTimeSpaceBest For
KruskalO(E log E)O(V)Sparse graphs, edge list input
Prim (binary heap)O(E log V)O(V)Dense graphs, adjacency list
Prim (Fibonacci heap)O(E + V log V)O(V)Very dense graphs
BorΕ―vkaO(E log V)O(V)Parallel implementation

🎯 What You'll Learn

After reading this article, you will be able to:

  • Implement Union-Find with path compression and union by rank
  • Apply Kruskal's algorithm for edge-based MST construction
  • Use Prim's algorithm for vertex-based MST growth
  • Understand MST properties and their proofs
  • Solve practical problems using MST (clustering, network design)
  • Choose the right algorithm based on graph characteristics

πŸ”₯ Production Story: The Network Infrastructure Optimization

A telecom company needed to connect 50 data centers with fiber optic cables. Running cables between all pairs would cost billions. They needed the minimum-cost network that still connected everything.

JAVA(18 lines)
Code
Loading syntax highlighter...
The problem: Full mesh is O(VΒ²) connections. With 50 centers, that's 1,225 connections at average $2M each = $2.45B.
The solution:
JAVA(35 lines)
Code
Loading syntax highlighter...
Additional consideration - redundancy:
JAVA(24 lines)
Code
Loading syntax highlighter...
The lesson: MST provides the minimum-cost connected network. Real applications often add redundancy on top of MST.

🧠 Mental Model: MST Properties

TEXT(37 lines)
Code
Loading syntax highlighter...

πŸ”¬ Deep Dive: Union-Find (Disjoint Set Union)

Basic Implementation

JAVA(69 lines)
Code
Loading syntax highlighter...

Union-Find Visualization

TEXT(31 lines)
Code
Loading syntax highlighter...

Union-Find with Size (Alternative to Rank)

JAVA(41 lines)
Code
Loading syntax highlighter...

πŸ”¬ Deep Dive: Kruskal's Algorithm

The Algorithm

JAVA(41 lines)
Code
Loading syntax highlighter...

Kruskal's Visualization

TEXT(24 lines)
Code
Loading syntax highlighter...

πŸ”¬ Deep Dive: Prim's Algorithm

Priority Queue Implementation

JAVA(57 lines)
Code
Loading syntax highlighter...

Prim's with Adjacency Matrix (Dense Graphs)

JAVA(41 lines)
Code
Loading syntax highlighter...

Prim's Visualization

TEXT(24 lines)
Code
Loading syntax highlighter...

πŸ”¬ Deep Dive: BorΕ―vka's Algorithm

Parallel-Friendly MST

JAVA(52 lines)
Code
Loading syntax highlighter...

Algorithm Comparison

AspectKruskalPrimBorΕ―vka
StrategySort edges, add if no cycleGrow tree from vertexEach component finds min edge
Data structureUnion-FindPriority QueueUnion-Find
Better forSparse graphsDense graphsParallel systems
Edge formatEdge listAdjacency listEdge list

πŸ”¬ Deep Dive: MST Applications

Clustering (Single-Linkage)

JAVA(58 lines)
Code
Loading syntax highlighter...

Network Design with Steiner Tree Approximation

JAVA(35 lines)
Code
Loading syntax highlighter...

Maximum Bottleneck Path

JAVA(51 lines)
Code
Loading syntax highlighter...

⚠️ Common Mistakes

Mistake 1: Union-Find Without Optimizations

JAVA(15 lines)
Code
Loading syntax highlighter...

Mistake 2: Forgetting MST Has V-1 Edges

JAVA(14 lines)
Code
Loading syntax highlighter...

Mistake 3: Not Handling Disconnected Graphs

JAVA(9 lines)
Code
Loading syntax highlighter...

Mistake 4: Wrong Prim's Priority Queue Update

JAVA(16 lines)
Code
Loading syntax highlighter...

πŸ› Debug This: The Broken MST

These implementations have bugs. Find and fix them:

JAVA(68 lines)
Code
Loading syntax highlighter...
πŸ’‘ Hint

Look for:

  1. Missing return assignment in path compression
  2. Missing cycle check before adding edge
  3. Missing check for inMST[px] == inMST[py] in union
  4. Order of operations in Prim's
βœ… Solution 
JAVA(88 lines)
Code
Loading syntax highlighter...
Bugs explained:
  1. Union-Find find(): find(parent[x]) without assignment doesn't compress path. Must be parent[x] = find(parent[x]).
  2. Kruskal's: Adding every edge without checking if union succeeds creates cycles and includes edges between already-connected vertices.
  3. Prim's: Must mark inMST[u] = true BEFORE updating neighbors, otherwise we might update keys of vertices we just processed. Also need to check !inMST[v] before updating key.

πŸ’» Exercises

Exercise 1: Min Cost to Connect All Points (LeetCode 1584) ⭐⭐

Connect all points with minimum total Manhattan distance.

JAVA(9 lines)
Code
Loading syntax highlighter...

Exercise 2: Number of Operations to Make Network Connected (LeetCode 1319) ⭐⭐

Find minimum cables to move to connect all computers.

JAVA(10 lines)
Code
Loading syntax highlighter...
πŸ’‘ Hint

Need at least n-1 cables. Extra cables (creating cycles) can be reused. Count components with Union-Find.

Exercise 3: Find Critical Edges in MST ⭐⭐⭐

Find edges that must be in every MST and edges that can be in some MST.

JAVA(9 lines)
Code
Loading syntax highlighter...

Exercise 4: Second Minimum Spanning Tree ⭐⭐⭐⭐

Find the MST with second smallest total weight.

JAVA(9 lines)
Code
Loading syntax highlighter...
πŸ’‘ Hint

For each edge in MST, try removing it and finding MST of remaining graph. Second MST is the minimum of these attempts (plus: for each edge not in MST, try adding it and removing one edge from the cycle formed).

Exercise 5: Minimum Cost to Reach Destination with Stops ⭐⭐⭐⭐

Combined MST and shortest path problem.

JAVA(9 lines)
Code
Loading syntax highlighter...

🎀 Interview Questions

Question 1: When would you use Kruskal's vs Prim's?

Answer:
Use Kruskal's when:Use Prim's when:
Sparse graph (E << VΒ²)Dense graph (E β‰ˆ VΒ²)
Edges given as listAdjacency list/matrix available
Need to process edges by weightStarting from specific vertex
Already have Union-FindDon't want Union-Find overhead
Complexity comparison:
  • Kruskal: O(E log E) - dominated by sorting
  • Prim (binary heap): O(E log V)
  • Prim (Fibonacci heap): O(E + V log V)
  • Prim (adjacency matrix): O(VΒ²)

For E β‰ˆ VΒ²: Prim's O(VΒ²) matrix version beats Kruskal's O(VΒ² log V). For E β‰ˆ V: Kruskal's and Prim's are comparable.

Question 2: Explain Union-Find optimizations

Answer:

Two optimizations make Union-Find nearly O(1):

1. Path Compression (in find):
JAVA(5 lines)
Code
Loading syntax highlighter...

Flattens tree during find operations.

2. Union by Rank/Size (in union):
JAVA(11 lines)
Code
Loading syntax highlighter...

Keeps trees balanced.

Combined complexity: O(Ξ±(n)) per operation, where Ξ± is inverse Ackermann function. For all practical n, Ξ±(n) ≀ 4.

Question 3: How would you find if an edge is in MST?

Answer:

Two approaches:

Method 1: Cut Property For edge (u,v), check if it's the minimum edge crossing some cut containing u on one side and v on the other.
Method 2: Cycle Property For edge (u,v) with weight w:
  1. Remove edge (u,v) from graph
  2. Find path from u to v
  3. If all edges on path have weight < w, edge is NOT in any MST
  4. If path has edge with weight > w, edge IS in some MST
Method 3: Build MST and Check
  1. Build MST using Kruskal's
  2. For edge not in MST: add it (creates cycle), check if it's max in cycle
  3. If it's the unique max, it's not in any MST
  4. If tied for max, it could be in some MST

Question 4: What are MST applications beyond network design?

Answer:
  1. Clustering: Single-linkage clustering removes k-1 longest MST edges for k clusters
  2. Image segmentation: Pixels as vertices, edge weights = difference. MST finds natural boundaries.
  3. Approximation algorithms: MST gives 2-approximation for Traveling Salesman (metric TSP)
  4. Taxonomy: Phylogenetic trees in biology
  5. Circuit design: Minimum wire length for connecting components
  6. Bottleneck paths: MST contains maximum-bottleneck path between any two vertices
  7. Maze generation: Random MST on grid creates perfect maze

Question 5: How do you handle MST with multiple edge weight ties?

Answer:

When edges have equal weights:

  1. MST may not be unique: Multiple valid MSTs with same total weight
  2. Kruskal's behavior: Among equal-weight edges, order is implementation-dependent (stable sort preserves input order)
  3. Finding all MSTs: Replace each tied edge with alternatives and enumerate
  4. Critical vs pseudo-critical edges:
    • Critical: Must be in every MST
    • Pseudo-critical: In some but not all MSTs
    • Neither: In no MST
JAVA(9 lines)
Code
Loading syntax highlighter...

πŸ“‹ Quick Reference

Union-Find Template

JAVA(23 lines)
Code
Loading syntax highlighter...

Kruskal's Template

JAVA(13 lines)
Code
Loading syntax highlighter...

Prim's Template

JAVA(20 lines)
Code
Loading syntax highlighter...

πŸ“… Review Schedule

DayFocusTime
Day 1Read article, implement Union-Find60 min
Day 3Implement Kruskal's from scratch30 min
Day 7Implement Prim's with priority queue30 min
Day 14Solve MST LeetCode problems45 min
Day 30Review and implement clustering20 min

πŸ”— What's Next?

Part 14: Advanced Graph Algorithms covers:
  • Strongly Connected Components (Tarjan, Kosaraju)
  • Articulation points and bridges
  • Max flow (Ford-Fulkerson, Edmonds-Karp)
  • Bipartite matching
Key insight preview: These algorithms reveal deep graph structure - which vertices/edges are critical, how information flows, and how to optimally match elements.
This article is part of the Algorithms Compendium series. For the complete learning path, see Part 0: How to Use This Series.

Tags:

MstKruskalPrimUnion-findNetwork Design
Last updated: June 10, 2026 at 11:12 AM