Kruskal's algorithm finds a minimum spanning tree of a weighted undirected graph: it takes the edges from lightest to heaviest and keeps each one that joins two separate trees, using union-find to skip those that would close a cycle. It runs in O(E log E) time. This page explains how it works, with a step-by-step animation of Kruskal's algorithm and its union-find forest from the VisiGrab app.
// how kruskal's algorithm works
Kruskal's algorithm finds a minimum spanning tree (MST) of a connected, weighted, undirected graph: a set of edges that joins every vertex without a cycle, at the least possible total weight. With V vertices the tree has V − 1 edges, and the algorithm returns them as a list. It is greedy, not dynamic programming: it always takes the lightest edge still allowed and never revisits a choice. Joseph Kruskal published it in 1956.
The edges chosen so far form a spanning forest: trees that between them hold every vertex and merge as edges are accepted.
1. Sort the edges: order them by weight, lightest first, so that every edge is met only after all the lighter ones.
2. Start the forest: put every vertex in a set of its own.
3. Take or skip the next edge: if its two vertices lie in different sets, add the edge to the tree and merge the two sets. If they share a set, skip the edge: it would close a cycle.
4. Stop at V − 1 edges: the forest is now one tree, and any further edge would close a cycle, so the rest of the list is never read.
Two vertices in the same set are already joined by chosen edges, directly or through several, so an edge between them would add a second route: a cycle.
The sets live in a union-find structure, also called a disjoint-set union (DSU). Each set is a tree of links whose root names the set. Find follows the links from a vertex up to its root, and two vertices share a set when their roots match. Union links one root under the other. With union by rank and path compression, both take almost constant amortized time. A graph search per edge would also catch the cycle, but at O(V) per edge.
The app's code, buildMst in Java and build_mst in Python and C++, takes the vertices and the edges and returns the tree's edges. In pseudocode:
buildMst(vertices, edges)
mst = empty list
sort edges by weight
uf = UnionFind(vertices)
for each edge (u, v) in edges
if uf.find(u) != uf.find(v)
mst.add(edge)
uf.union(u, v)
if size(mst) == V - 1
break
return mst
The test uf.find(u) != uf.find(v) is the cycle check: different roots mean different trees, so the edge joins mst and uf.union(u, v) merges the two sets. A skipped edge costs only its two finds. V is the number of vertices, and break ends the loop once size(mst) == V - 1.
The player below runs Kruskal's algorithm on the app's default graph, with the union-find forest on the right. Five edges form a minimum spanning tree of weight 63, and the four heaviest edges are never examined. The forest records sets, not tree edges: after DC, B hangs under A, yet the tree joins A and B only through D and C, and the edge AB is skipped.
It skips any edge whose two ends already share a union-find set: chosen edges already join them, so the edge would close a cycle. The player skips AB this way at step 20.
So that each edge it accepts is the lightest edge leaving the tree of either end, which the cut property proves safe to keep. Without the sort, a heavier edge could join two trees first; a lighter edge between the same two trees would then be skipped as closing a cycle, and the result would not be a minimum spanning tree.
The cut property: split the vertices into two groups, and the lightest edge between the groups belongs to a minimum spanning tree. Each edge Kruskal takes is the lightest edge leaving the tree of either of its ends: a lighter one would have come first and, as its ends are still in different sets, would have been taken. When the player takes BE, at 27, it is the lightest edge between {A, B, C, D} and {E, F}. Adding BE to a spanning tree that lacks it closes a cycle with a heavier edge between the groups; dropping that edge leaves a lighter tree.
The cycle property: with distinct weights, the heaviest edge on a cycle belongs to no minimum spanning tree. AB would close the cycle A → D → C → B → A, and at 14 it outweighs AD, DC and BC. Every edge Kruskal skips is the heaviest on the cycle it would close, since the others came first.
With distinct weights, as in the player, the minimum spanning tree is unique. With equal weights there can be several, and the order the sort gives the tied edges decides which one is returned.
Sorting the E edges takes O(E log E). The finds and unions add O(E α(V)), where α, the inverse Ackermann function, grows so slowly that it is effectively a small constant. Sorting dominates, so the total is O(E log E), which is the same as O(E log V): a simple graph has fewer than V2 edges, so log E is less than 2 log V.
Edges that come already sorted leave only O(E α(V)). The early stop saves finds, not the sort; a min-heap of the edges, built in O(E), pops only the edges examined, at O(log E) each, so the edges never reached are never sorted. Extra space is O(V) for the sets and O(E) for the sorted edges.
Both are greedy and both return a minimum spanning tree, the same one when no two weights are equal. Kruskal takes the lightest safe edge anywhere, so its trees stand apart until they merge, while Prim's algorithm grows one tree from a start vertex; Kruskal suits sparse graphs and edge lists, Prim's array version dense graphs. Full comparison →
A minimum spanning tree makes the total weight of its edges as small as possible and has no source. Dijkstra's algorithm builds a shortest-path tree, which makes each vertex's distance from one source as small as possible. In the player's tree, C reaches E through B, a route of weight 37, while the shortest path from C to E is the edge CE, at 30.
The app's listing is the pseudocode above in each language, with the library sort. The full source on GitHub, in Python, Java and C++, adds the union-find class, with union by rank and path compression.
Note
C++'s std::sort is not stable: edges of equal weight may leave it in any order, so the C++ code may take a different one of them than the Java and Python code, whose sorts keep the input order. The tree can differ; its weight cannot.
// in the app
In VisiGrab, Kruskal's algorithm works through four example graphs, with its union-find forest merging beside each graph and a sentence for every step.
The Examples dialog offers four six-vertex graphs with Kruskal's own weights and remembers your pick. In each, one edge is skipped because it would close a cycle, and the run stops before the four or five heaviest edges.
In the Graph Constructor, choose MST, draw a connected graph of up to 12 vertices with weights from 1 to 99, tap Apply and switch to Kruskal. Each Next adds one tree edge and lists the edges taken so far, and Prim on the same graph is one switch away.
The Info tab walks through the algorithm in four numbered stages with six illustrations, from the sorted row of edges to an edge that would close a cycle, and ends with a summary against Prim. The Efficiency tab adds up the sort and the union-find work to O(E log E).
The listing sorts the edges, keeps each one whose ends have different roots, merges their sets and stops at V − 1 edges. Three numbered notes cover the sort, the cycle check and the union, and the full source is one link away on GitHub, with the union-find class in the file beside it.
Eight questions, every option explained: what comes first, what a spanning forest is, the starting sets, an edge inside one set, when the run may stop, how Prim differs, which graphs suit it and what dominates the running time.
Union-Find has a topic of its own: tap two of nine nodes to merge their sets, while its info dialog demonstrates union by rank and path compression. Prim's topic grows a minimum spanning tree from one vertex on the same four layouts, with weights of its own.
// build your own
Download VisiGrab to watch the union-find forest merge into one tree on four example graphs, then draw a weighted graph of your own and build its minimum spanning tree.
Kruskal's algorithm is one of 30+ topics. See them all