Kruskal's algorithm
medium'Would this edge close a cycle?' is exactly 'are these two vertices already connected?' - which is what Union-Find answers in near-constant time.
O(E log E)Space O(V)Saved in this browser - no sign-up, nothing sent anywhere.
How kruskal's algorithm works
Kruskal builds a minimum spanning tree by global greed: sort every edge by weight, then walk the list taking any edge whose endpoints are not yet connected and skipping any that would close a cycle. Accepted edges merge fragments of a growing forest; after V-1 acceptances the forest is one tree.
The cut property is why greed is safe. Split the vertices any way you like: the lightest edge crossing the split belongs to some minimum spanning tree. When Kruskal examines an edge joining two components, that edge is the lightest one crossing that particular split - everything lighter was already taken or rejected inside a component.
The cycle test is the expensive-looking part, and Union-Find makes it nearly free: 'would this edge close a cycle?' is exactly 'do find(u) and find(v) agree?'. That leaves the initial sort as the true cost, O(E log E) - the loop after it is effectively linear.
Step by step
- Sort the 10 edges ascending: G-H at weight 1 first, then A-D and C-F at 2, B-E and E-H at 3, and so on.
- G-H, A-D, C-F, B-E: four accepts in a row, each merging two singletons into a two-vertex fragment.
- E-H at weight 3 bridges two fragments - the pair B, E and the pair G, H become one four-vertex component.
- A-B at weight 4 merges that component with A, D. Six vertices connected; C and F still sit apart.
- E-F at weight 4 pulls in the last fragment. That is acceptance number 7 - exactly V-1 for 8 vertices - so the tree is complete.
- The early exit fires: D-E, B-C and D-G are never even examined. Total weight 1 + 2 + 2 + 3 + 3 + 4 + 4 = 19.
Complexity
| Worst case time | O(E log E) |
|---|---|
| Space | O(V) |
The sort dominates; the cut property proves the greedy choice is safe.
Reference implementation
Python
def kruskal(n, edges):
"""edges: list of (weight, u, v)."""
edges = sorted(edges)
dsu = DSU(n)
mst, total = [], 0
for w, u, v in edges:
if dsu.union(u, v): # union returns False if already joined
mst.append((u, v, w))
total += w
if len(mst) == n - 1:
break
return mst, totalJavaScript
function kruskal(n, edges) {
edges.sort((a, b) => a.w - b.w);
const dsu = new DSU(n);
const mst = [];
let total = 0;
for (const { u, v, w } of edges) {
if (dsu.union(u, v)) {
mst.push({ u, v, w });
total += w;
if (mst.length === n - 1) break;
}
}
return { mst, total };
}Worth noticing
Greedy, and provably correct
Always take the cheapest edge that does not close a cycle. The cut property guarantees this is safe: for any way of splitting the vertices in two, the lightest edge crossing the split belongs to some minimum spanning tree.
Union-Find is what makes the cycle check cheap
'Would this edge close a cycle?' is exactly 'are these two vertices already connected?'. DSU answers it in near-constant time; without it you would run a traversal per edge and the algorithm would be O(E·V).
Stop at V−1 edges
A spanning tree on V vertices has exactly V−1 edges. Once you have that many the tree is complete and the remaining edges cannot help - a useful early exit on dense graphs.
Kruskal versus Prim
Kruskal sorts edges globally and grows a forest that merges. Prim grows one connected tree from a seed. Kruskal suits sparse graphs and edge lists; Prim suits dense graphs and adjacency structures.
Common pitfalls
- Checking cycles with anything but Union-Find. A DFS per edge makes the loop O(E·V); a naive 'both endpoints seen' test wrongly rejects edges joining two separate fragments.
- Forgetting the graph can be disconnected. If the loop ends with fewer than V-1 accepted edges there is no spanning tree - you built a minimum spanning forest.
- Skipping the V-1 early exit. Still correct, but on dense graphs you pointlessly examine the long expensive tail of the sorted list.
- Assuming the MST is unique. With duplicate weights - two 2s, two 3s and two 4s here - different tie orders can pick different edges, though the total is always 19.
- Sorting by the wrong field or mutating weights mid-run. The correctness proof lives entirely in the ascending order; break it and greed stops being safe.
Where it is used
- Network design: connecting offices, substations or houses with minimum total cable, pipe or fibre.
- Single-linkage clustering: stop after V-k acceptances and the remaining fragments are k clusters.
- Image segmentation via graph-based methods, merging pixel regions cheapest-boundary first.
- Interviews: Min Cost to Connect All Points, and any problem whose answer is an MST weight.
Frequently asked questions
What is the time and space complexity of Kruskal's algorithm?
O(E log E), and the sort is essentially all of it - the main loop's E Union-Find operations run in amortised near-constant time. Since E is at most V², log E is within a factor of 2 of log V, so O(E log V) names the same bound. Space is O(V) for the disjoint-set arrays.
Why doesn't Kruskal's greedy choice go wrong?
The cut property: for any partition of the vertices into two groups, the lightest edge crossing between them is in some minimum spanning tree. Every edge Kruskal accepts is the lightest crossing the cut between the two components it merges, so every acceptance is provably safe.
Kruskal or Prim - which should I use?
Same answer, different shapes. Kruskal wants an edge list and suits sparse graphs - sort once, then near-linear. Prim wants an adjacency structure and a priority queue, and suits dense graphs. If the edges arrive pre-sorted or you already maintain Union-Find, Kruskal is the natural fit.
What happens if edge weights are equal?
Nothing breaks. Ties can be broken arbitrarily; different tie-breaks may produce different trees, but every one has the same minimum total weight. When all weights are distinct the MST is unique - a favourite follow-up question in interviews.