What is Kruskal's Algorithm?
Minimum Spanning Tree
A subset of edges that connects all vertices in a weighted, undirected graph with the minimum possible total weight, without forming any cycles.
Greedy Approach
Kruskal's algorithm sorts all edges by weight and picks the smallest edge that doesn't form a cycle. It repeats until V−1 edges are selected.
Union-Find (DSU)
Uses the Disjoint Set Union data structure with path compression and union by rank to efficiently detect cycles in near-constant time.
How It Works — Step by Step
Sort All Edges
Arrange all edges in non-decreasing order of their weight using a sorting algorithm (O(E log E)).
Initialize Union-Find
Create a parent array where each vertex is its own parent. This forms V disjoint sets initially.
Pick Smallest Edge
Take the next smallest edge. Check if adding it would form a cycle using the find() operation.
Add or Reject
If no cycle → add the edge to MST and perform union(). If it forms a cycle → reject it.
Repeat Until Done
Continue until MST has exactly V − 1 edges. The total weight of selected edges is the minimum cost.
Complexity Analysis
Time Complexity Breakdown
α(V) = Inverse Ackermann function ≈ constant for all practical inputs
Kruskal's vs Prim's — Comparison
| Property | Kruskal's | Prim's |
|---|---|---|
| Approach | Edge-based (global) | Vertex-based (local) |
| Data Structure | Union-Find (DSU) | Priority Queue / Min-Heap |
| Time Complexity | O(E log E) | O(E log V) |
| Best For | Sparse graphs (E ≈ V) | Dense graphs (E ≈ V²) |
| Works on Disconnected? | Yes (finds MSF) | No |
| Needs Sorting? | Yes | No |
Kruskal's Algorithm — Test Cases
Edges: A-B=1, B-C=2, A-C=4
Edges: A-B=1, A-C=3, B-C=2, B-D=4, C-D=2
Edges: 1-2=5, 2-3=5, 3-4=5, 1-4=5, 1-3=5
Edges: A-B=2, C-D=3 (no edges between the pairs)
Edges: 1-2=2, 1-3=3, 2-3=1, 2-4=4, 3-5=5, 4-5=1, 3-4=2
Edges: A-B=5, B-C=3, C-D=8, D-E=2
Key Rules to Remember
| Condition | Behavior |
|---|---|
| N nodes | MST has exactly N − 1 edges |
| Cycle formed | Skip that edge |
| Disconnected graph | Result is a forest, not a single MST |
| Tie in weights | Either edge can be chosen |
Kruskal's Algorithm — Real-World Applications
Network Design (Computer Networks)
Connect computers/servers with minimum cable length for LAN/WAN and data centers.
Electrical Power Grids
Lay power lines between cities and substations at minimum cost.
Water Supply & Pipeline Systems
Design pipelines across neighborhoods with minimal pipe length.
Road & Transportation Planning
Connect cities and hubs with minimum total road distance or cost.
Airlines & Logistics
Build a minimum-cost route network for flights and deliveries.
Biology & Bioinformatics
Cluster genes and build phylogenetic trees using MST-based clustering.
Image Processing & Computer Vision
Segment images by grouping similar pixels using MST clustering.
Telecommunication Networks
Lay fiber optics and connect towers at minimum cost.
Machine Learning — Clustering
Perform hierarchical clustering and customer segmentation.
Game Development
Generate connected maps and efficient NPC path networks.
Quick Summary Table
| Domain | Real Entity | Edge Weight |
|---|---|---|
| Networking | Computers / Servers | Cable length / latency |
| Power Grid | Cities / Substations | Wire cost |
| Roads | Cities / Towns | Distance / cost |
| Water Supply | Neighborhoods | Pipe cost |
| Airlines | Airports | Ticket cost / distance |
| Biology | Species / Genes | Genetic difference |
| Telecom | Cell Towers | Fiber cable cost |
| ML Clustering | Data Points | Similarity distance |