Kruskal's algorithm explained for minimum spanning trees

When you are faced with a graph full of nodes and weighted edges and you want to connect everything with the smallest possible total cost, the minimum spanning tree is the answer. A spanning tree of a connected graph touches every vertex with exactly n−1 edges, and a minimum spanning tree, commonly abbreviated MST, is the spanning tree whose sum of edge weights is smallest among all candidates. The concept shows up everywhere: in laying fibre-optic cable between suburbs, in clustering customers for a recommendation pipeline, and in designing low-power sensor networks across regional Australia.

The problem has been studied since the 1920s, when Otakar Borůvka was looking for the most economical way to construct an electrical grid in Moravia. In 1956, Joseph Kruskal published his elegant greedy approach, which became one of the canonical ways to solve the problem. Alongside Prim's algorithm and the older Borůvka method, Kruskal's algorithm still appears in modern interview preparation, in graph libraries, and in production code that needs to be correct under tight time budgets.

This tutorial walks through Kruskal's algorithm from intuition to implementation. You will see the pseudocode, the data structure that makes the algorithm fast, a Python sketch you can adapt, and a few examples grounded in Australian contexts such as telecommunications, transport corridors, and large-scale logistics networks. A short discussion of complexity, pitfalls, and the role of NumPy array operations closes the article.

The intuition behind minimum spanning trees

A spanning tree is a connected acyclic subgraph that covers every vertex of the original graph. If the original graph has n vertices, any spanning tree has exactly n−1 edges, because removing any edge from a spanning tree disconnects the graph, and adding any edge creates a cycle. The minimum spanning tree minimises a linear objective: the total weight.

Kruskal's algorithm solves this problem greedily. At every step, it picks the cheapest edge that does not create a cycle. The greedy choice is safe because the cut property of MSTs guarantees that the cheapest edge crossing any cut belongs to some minimum spanning tree. As long as you keep adding globally cheapest edges that respect acyclicity, you cannot miss the optimal answer.

This kind of reasoning explains why Kruskal's algorithm is taught alongside other classic greedy procedures. For Australian readers, the simplest mental model is a road planner laying the cheapest possible set of regional highways between towns such as Dubbo, Tamworth, Bathurst, Mudgee and Orange, where every road costs money and any closed loop would waste the budget. Each new road connects the cheapest available pair, and the planner stops when every town is reachable.

The greedy approach is unusual in that it gives an exact, provably optimal answer for an NP-easy problem without backtracking, dynamic programming, or linear programming. The reason it works is the matroid structure of forests themselves, which puts MST problems in the same family of optimisable systems as scheduling tasks or selecting projects.

Walking through the algorithm step by step

Kruskal's algorithm is refreshingly short. The input is a connected, undirected graph with n vertices and m edges, each carrying a non-negative weight. The output is an MST with n−1 edges. There are three high-level steps.

First, sort every edge in the graph by its weight in non-decreasing order. Sorting is the most expensive single operation in the entire procedure, and it determines the overall asymptotic complexity. Second, initialise a disjoint set data structure, also known as Union-Find, where each vertex lives in its own singleton set. Third, iterate through the list of edges in sorted order. For each edge (u, v) with weight w, check whether u and v belong to the same set. If they do, adding the edge would create a cycle, so skip it. If they do not, add the edge to the MST and merge the two components by performing a union operation on u and v. Repeat until the MST contains n−1 edges.

Here is a compact pseudocode version.

function kruskal(graph):
    sort graph.edges by weight ascending
    mst = []
    uf = new UnionFind(graph.vertices)
    for each edge (u, v, w) in graph.edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, w))
        if len(mst) == graph.num_vertices - 1:
            break
    return mst

The order of edge inspection matters, and the sort is what makes Kruskal deterministic. Because the algorithm only needs to know which edges have been added and which components remain, it does not require the graph to be represented in any specific way. Adjacency lists, edge lists, and even externally stored CSV files work equally well. This flexibility is one reason Kruskal is a common choice when the edges are not all in memory at once, such as when processing very large logistics or telecommunications graphs.

Union-Find as the engine of cycle detection

The correctness of Kruskal rests on the Union-Find structure, also called Disjoint Set Union. Union-Find maintains a partition of vertices into disjoint sets and supports two operations: find, which returns the canonical representative of a vertex's component, and union, which merges two components. A well-engineered Union-Find makes both operations effectively amortised constant time.

There are two optimisations you should always apply. The first is path compression: during a find, recursively rewrite every visited parent pointer to point directly at the root. The second is union by rank or size, which attaches the shorter tree under the taller one to keep the trees shallow. With both techniques, the amortised cost of m operations on n elements is O(m α(n)), where α is the inverse Ackermann function and stays tiny for any realistic input size. For an Australian engineer piping billions of edges through a pipeline, this constant factor difference can mean minutes versus days.

A common mistake is to use a naive linear search to detect cycles. That works correctly but turns the algorithm into O(E V), which is unacceptable on anything but toy graphs. Whenever you implement Kruskal, you must use a real Union-Find, and you should not skip the path compression step.

If you enjoy squeezing more performance out of Python without dropping to C, you will appreciate this NumPy broadcasting guide, which explains how vectorisation can complement a tight Union-Find in larger pipelines. Broadcasting does not replace Union-Find for cycle detection, but it is a useful trick when you want to vectorise parts of the preprocessing, such as computing edge weights from a dense cost matrix.

Complexity analysis and Python implementation

The complexity of Kruskal's algorithm splits into three pieces. Sorting all edges costs O(E log E). For a connected graph, E is at least V−1 and at most V(V−1)/2, so E log E = O(E log V). Each Union-Find operation amortises to O(α(V)) ≈ O(1). With E such operations, the total time is O(E log E), dominated by the sort. Space is O(V + E) for the edges and the Union-Find arrays.

A clean reference in idiomatic Python looks like this.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True


def kruskal(n, edges):
    edges = sorted(edges, key=lambda e: e[2])
    uf = UnionFind(n)
    mst = []
    for u, v, w in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
            if len(mst) == n - 1:
                break
    return mst

Two practical pitfalls. First, do not run Kruskal on a graph that is not connected; the algorithm will simply stop early and return a minimum spanning forest. Detect this with a counter and raise an explicit error rather than silently returning a partial tree. Second, weights should be non-negative for the greedy proof to hold. Negative weights still yield the correct tree for the MST problem, but if you ever extend the technique to directed arborescences, check the assumptions again.

For background on the editorial standards behind these tutorials, you can read About hello ML, which describes the community's commitment to clarity, reproducibility, and code that runs out of the box.

Practical applications and an Australian context

Minimum spanning trees show up in a surprising number of real Australian projects. In telecommunications, the National Broadband Network requires laying fibre across sparsely populated regions, and an MST tells you the minimum-cost backbone that still touches every planned node. In mining, companies such as BHP and Rio Tinto build private rail and conveyor networks across the Pilbara, where MST computations help minimise truck route lengths and fuel use. In urban planning, the Greater Sydney Commission and the Victorian Department of Transport have used MST-based clustering to group suburbs that share commuting ties, helping to plan new train corridors and bus priority routes.

The algorithm also plays a quiet role in machine learning pipelines. Single-linkage hierarchical clustering, used in customer segmentation and anomaly detection, is a direct descendant of MST construction. So is the k-clustering variant, where you stop after adding edges until you have exactly k components. For a data scientist in Melbourne working on churn prediction, an MST over a graph of customers and similarity edges yields clusters that respect local density without needing a pre-specified distance threshold.

Privacy and data-handling considerations matter here too. Under the Privacy Act 1988, any graph that links identifiable Australians must be de-identified before MST analysis is shared or published, especially when edges encode locations, demographics, or transactional behaviour. The Notifiable Data Breaches scheme adds further obligations if a derived MST dataset is exposed. Treating weights as abstractions rather than raw coordinates is a good default for any production system.

If you ever pause between MST runs and look for a slightly different algorithmic puzzle, this keno for cents review is a curious detour into probabilistic systems that share the same flavour of greedy decision making under uncertainty, even if the domain is very different. It is a useful reminder that greedy intuition, when paired with a matroid or a martingale, can travel between disciplines.

Finally, a quick checklist before you ship a Kruskal implementation. Confirm your input is undirected, or duplicate every directed edge. Initialise Union-Find with the correct number of vertices. Make sure your sort is stable or, better, deterministic on ties. Validate the resulting tree has exactly V−1 edges. And remember that the algorithm gives an MST only because the graph obeys the cut property. If your problem breaks that property, such as a constrained Steiner tree, you will need a different tool.