Kruskal Algorithm
A greedy algorithm that builds a minimum spanning tree by adding the cheapest edges that avoid cycles
Kruskal's algorithm is a greedy algorithm for finding a minimum spanning tree of a connected, weighted graph by sorting all edges by weight and adding each one, in order, as long as it doesn't create a cycle.
Definition
Kruskal's algorithm is a greedy algorithm for finding a minimum spanning tree of a connected, weighted graph by sorting all edges by weight and adding each one, in order, as long as it doesn't create a cycle.
Overview
Kruskal's algorithm, published by Joseph Kruskal in 1956, takes an edge-centric view of the minimum spanning tree problem: rather than growing a single connected tree outward, it considers all of the graph's edges globally, sorted from cheapest to most expensive, and greedily accepts each edge unless doing so would close a cycle. Because it processes edges independent of any notion of a growing connected component, at any point during execution the accepted edges form a forest — potentially several disjoint tree fragments — that only becomes a single spanning tree once enough edges have been added to connect every vertex. The key implementation challenge is efficiently answering "would adding this edge create a cycle" for each candidate edge, and this is where the Union-Find (Disjoint-Set Union) data structure becomes essential: each vertex starts in its own singleton set, and an edge is safe to add exactly when its two endpoints belong to different sets, at which point the algorithm merges (unions) those two sets. With Union-Find optimized by union-by-rank and path compression, each cycle check runs in near-constant amortized time, so the algorithm's total running time is dominated by the initial edge sort, giving an overall complexity of O(E log E), equivalent to O(E log V) since E is at most V². Kruskal's algorithm's correctness follows directly from the cut property of minimum spanning trees: by always choosing the globally cheapest available edge that doesn't create a cycle, it never has to backtrack or reconsider a choice, which is what makes it a genuine (and provably optimal) greedy algorithm rather than a heuristic. It's typically preferred over Prim's algorithm when a graph is sparse (relatively few edges relative to vertices), since sorting a smaller edge list is comparatively cheap, while Prim's algorithm tends to be favored for dense graphs where its priority-queue-based approach scales better relative to vertex count.
Key Concepts
- Greedy algorithm that processes edges globally, sorted by ascending weight
- Adds each edge unless it would create a cycle with already-accepted edges
- Relies on a Union-Find data structure for efficient cycle detection
- Maintains a forest of tree fragments until the final spanning tree is complete
- Achieves O(E log E) time, dominated by the initial edge sort
- Correctness guaranteed by the cut property of minimum spanning trees
- Well suited to sparse graphs with relatively few edges
- Published by Joseph Kruskal in 1956
Use Cases
Frequently Asked Questions
From the Blog
Feature Engineering: Turning Data Into Signal
Feature engineering turns raw columns into inputs a model can actually learn from. Learn the core techniques that often matter more than the algorithm itself.
Read More ProgrammingWhat Is Big O Notation? A Beginner Guide
Big O notation describes how an algorithm's time or memory grows as input size increases. Learn the common complexities and how to analyze your own code.
Read More Data ScienceWhat Is Feature Engineering in Machine Learning?
Feature engineering is transforming raw data into inputs that help models learn. Good features often matter more than the algorithm. Learn the core techniques here.
Read More AI & TechnologyWhat Is Gradient Descent Explained for Beginners
Gradient descent is the algorithm that trains most machine learning models by repeatedly nudging parameters in the direction that reduces error, step by step.
Read More