Kruskal's Algorithm and the Minimum Spanning Tree Explained
For anyone who has tried to wire up a network of sensors across a sprawling wheat station outside Perth, or to lay fibre along the rail corridors between Sydney and Newcastle, the underlying question is the same: how do you connect everything with the least amount of cabling? That question is a Minimum Spanning Tree problem, and Kruskal's algorithm is one of the cleanest ways to solve it.
Kruskal's algorithm belongs to a family of greedy procedures that build a spanning tree by picking the cheapest edge that does not create a cycle. It works on any undirected, weighted graph, which makes it useful for road planning between regional towns, designing power grids in remote Queensland communities, or even clustering customers for an Australian e-commerce fulfilment centre. Its mechanics are simple enough to describe on a whiteboard in a Melbourne tutorial, yet powerful enough to handle graphs with millions of edges.
The Core Idea Behind Kruskal's Algorithm
A Minimum Spanning Tree (MST) of a connected, undirected graph is a subset of edges that touches every vertex, contains no cycles, and has the lowest possible total weight. Kruskal's algorithm sorts every edge by weight in ascending order and then walks through the list, adding each edge to the growing tree as long as it does not form a cycle with the edges already chosen.
The greedy choice works because of the cut property. Whenever Kruskal considers the lightest edge crossing some cut of the graph, that edge must belong to at least one MST. By applying this property repeatedly, the algorithm guarantees an optimal result without needing to look ahead. This simplicity is one reason the algorithm is taught alongside the basics of algorithms on foundations courses across universities in Adelaide and Melbourne, where students often code it up before moving on to more advanced graph problems.
What makes Kruskal distinctive compared with Prim's algorithm is that it does not need to maintain a single connected component as it runs. It happily considers edges between distant vertices, which is convenient when the graph is sparse, such as a freight network linking ports in Fremantle, Botany Bay and the Port of Brisbane. The algorithm also exposes a natural parallelism: edges can be sorted once and distributed across workers without changing the final answer.
How the Union-Find Structure Keeps Things Cycle-Free
The only data structure Kruskal really needs beyond the sorted edge list is a disjoint-set, commonly called Union-Find. Each vertex starts in its own set, and the algorithm exposes two operations: Find, which returns the representative of a vertex's set, and Union, which merges two sets when an edge is accepted.
Before adding an edge (u, v), Kruskal calls Find(u) and Find(v). If the two vertices belong to the same set, accepting the edge would close a cycle, so the algorithm discards it. If they belong to different sets, the edge is kept and Union(u, v) merges the two components. Path compression in Find and union by rank keep both operations effectively constant amortised, even on graphs that grow into the millions of vertices.
For larger Australian deployments, such as a nationwide fleet routing model used by a logistics company operating between Cairns and Hobart, this discipline matters. Without efficient Union-Find, the cycle check would dominate the runtime and the algorithm would lose its appeal compared with alternative approaches. Readers who already optimise SQL queries with indexing and explain plans will recognise the same principle of pushing the heavy work into a fast structural helper rather than re-deriving it on every iteration.
Walking Through a Worked Example
Consider a small graph with six vertices labelled A through F and the following weighted edges after sorting from lightest to heaviest: A-B (2), C-D (3), A-C (4), B-D (5), D-E (6), A-F (7), B-E (8), C-F (9), E-F (10).
The algorithm starts by accepting A-B, then C-D, then A-C. After these three edges, vertices A, B and C all live in the same component, while D is alone. The next candidate, B-D, connects the {A,B,C} component with D, so it is accepted and the union grows to {A,B,C,D}. Edge D-E is then added, growing the component to five vertices. The final missing vertex F is reached through edge A-F.
The accepted edges are A-B, C-D, A-C, B-D, D-E and A-F, with a total weight of 27. Every other edge either connects vertices already in the same set or, by the time it is considered, the spanning tree is already complete. The shape mirrors what an MST often looks like in practice: a slightly messy but cheap backbone that prefers short hops over long detours, a familiar pattern when tracing the rail map between regional NSW towns.
Comparing Kruskal with Prim's Algorithm
Both algorithms produce a minimum spanning tree, but their mechanics differ enough that one is usually preferable depending on the graph. The table below summarises the trade-offs that come up when teaching the topic or reviewing code in a working group.
| Aspect | Kruskal's Algorithm | Prim's Algorithm |
|---|---|---|
| Strategy | Edge-based, processes globally sorted edges | Vertex-based, grows one connected component |
| Best suited for | Sparse graphs | Dense graphs |
| Data structure | Union-Find for cycle detection | Priority queue or min-heap |
| Implementation complexity | Simple, especially with Union-Find | Slightly more involved with the heap |
| Typical time complexity | O(E log E) | O(E + V log V) with a Fibonacci heap |
| Sensitivity to edge count | Lower when E is close to V | Lower when E is close to V² |
| Sensitivity to vertex count | Linear in V | Dominated by heap updates |
| Use case preference | Distributed graphs, offline sort | Real-time single-source growth |
In practice, an Australian team choosing between the two often picks Kruskal when the edge list is already available and can be sorted once, and Prim when the graph is presented one vertex at a time, for instance from a streaming sensor feed across a mining lease in the Pilbara. The decision is rarely about correctness, since both deliver an MST, and almost always about how the input data arrives and what supporting structures are already in the codebase.
Practical Tips, Pitfalls and Extensions
A few habits save a lot of debugging time. First, always sort the edges using a stable comparator when weights tie, because the algorithm is correct for any tie-breaking but downstream code may not be. Second, size the Union-Find arrays up front rather than reallocating per edge, which removes a surprising amount of overhead in long pipelines. Third, log the accepted edges so the MST can be audited later, a practice that resonates with the documentation culture encouraged in SQL optimisation reviews on the same site.
A common pitfall is forgetting that Kruskal's algorithm assumes the graph is connected. If the input has multiple components, the result is a Minimum Spanning Forest, one tree per component, and the algorithm silently returns it without warning. Another pitfall is using a naive Find without path compression, which degrades the runtime from near-linear to roughly logarithmic per call, and that gap widens quickly on graphs with millions of edges such as the road network of New South Wales.
Variations exist for richer scenarios. A Maximum Spanning Tree uses the same algorithm with edges sorted in descending order, handy for capacity planning on transmission lines. A Minimum Spanning Tree in a graph with vertex weights can be approximated by splitting each vertex into an edge of equivalent cost. K-clustering, where the algorithm is stopped after V − k edges have been accepted, is widely used to split a customer base into segments for a Sydney-based retail analytics team.
Kruskal's algorithm remains popular because it maps cleanly onto real engineering constraints: a sorted list of candidates, a yes/no decision per candidate, and a small bookkeeping structure. Once the pattern is internalised, it shows up everywhere from laying NBN backhaul across regional Victoria to clustering documents in a Canberra research lab, and the same greedy logic keeps producing optimal results wherever the cost of connection is the bottleneck.