Kruskal's Algorithm, step by step.

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

What is Kruskal's algorithm?

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.

How does Kruskal's algorithm work? Sort, check, merge

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.

How Kruskal's algorithm detects cycles with union-find

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.

Kruskal's algorithm pseudocode

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.

Kruskal's algorithm example: the union-find forest step by step

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.

Kruskal's algorithm on a weighted graph

All steps as text
  1. Consider a weighted undirected graph. Build its minimum spanning tree by examining the edges in ascending order, starting with the lightest.
  2. Examine the edge EF.
  3. Use the Union-Find data structure to check whether the vertices E and F, connected by this edge, belong to the same set or different sets.
  4. Because its vertices belong to different sets, the edge EF cannot form a cycle and is therefore added to the collection of edges that will eventually form the MST. These edges are highlighted in yellow.
  5. To reflect this, the roots of the sets containing vertices E and F are merged in the Union-Find data structure, forming a larger tree in the spanning forest.
  6. Examine the edge AD.
  7. Use the Union-Find data structure to check whether the vertices A and D, connected by this edge, belong to the same set or different sets.
  8. Because its vertices belong to different sets, the edge AD cannot form a cycle and is therefore added to the collection of edges that will eventually form the MST. These edges are highlighted in yellow.
  9. To reflect this, the roots of the sets containing vertices A and D are merged in the Union-Find data structure, forming a larger tree in the spanning forest.
  10. Examine the edge BC.
  11. Use the Union-Find data structure to check whether the vertices B and C, connected by this edge, belong to the same set or different sets.
  12. Because its vertices belong to different sets, the edge BC cannot form a cycle and is therefore added to the collection of edges that will eventually form the MST. These edges are highlighted in yellow.
  13. To reflect this, the roots of the sets containing vertices B and C are merged in the Union-Find data structure, forming a larger tree in the spanning forest.
  14. Examine the edge DC.
  15. Use the Union-Find data structure to check whether the vertices D and C, connected by this edge, belong to the same set or different sets.
  16. Because its vertices belong to different sets, the edge DC cannot form a cycle and is therefore added to the collection of edges that will eventually form the MST. These edges are highlighted in yellow.
  17. To reflect this, the roots of the sets containing vertices D and C are merged in the Union-Find data structure, forming a larger tree in the spanning forest.
  18. Examine the edge AB.
  19. Use the Union-Find data structure to check whether the vertices A and B, connected by this edge, belong to the same set or different sets.
  20. The edge AB is not added to the collection because its vertices already belong to the same set. Adding it would create a cycle.
  21. Examine the edge BE.
  22. Use the Union-Find data structure to check whether the vertices B and E, connected by this edge, belong to the same set or different sets.
  23. Because its vertices belong to different sets, the edge BE cannot form a cycle and is therefore added to the collection of edges that will eventually form the MST. These edges are highlighted in yellow.
  24. The roots of the sets containing vertices B and E are merged. With this step, the forest reaches V − 1 edges, forming a single spanning tree — the MST is complete.
  25. The minimum spanning tree has the edges EF, AD, BC, DC, BE, with a total weight of 6 + 9 + 10 + 11 + 27 = 63. The heavier edges CE, BD, DE, CF were never examined.
Kruskal's algorithm on a weighted graph. Last step: The minimum spanning tree has the edges EF, AD, BC, DC, BE, with a total weight of 6 + 9 + 10 + 11 + 27 = 63. The heavier edges CE, BD, DE, CF were never examined.

How does Kruskal's algorithm avoid cycles?

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.

Why does Kruskal's algorithm sort the edges?

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.

Why Kruskal's algorithm works: proof by the cut and cycle properties

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.

Kruskal's algorithm time and space complexity

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.

Kruskal vs Prim: which is better?

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 →

Kruskal vs Dijkstra: minimum spanning tree vs shortest path

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.

Kruskal's algorithm on disconnected graphs, negative weights and directed graphs

  • Disconnected graphs: the tree never reaches V − 1 edges, so the loop runs through every edge and returns a minimum spanning forest, one tree per component.
  • Negative weights: allowed. Only the order of the weights matters.
  • Directed graphs: not supported. The directed problem, a minimum spanning arborescence, needs the Chu-Liu/Edmonds algorithm.
  • Maximum spanning tree: sort the edges heaviest first.

Kruskal's algorithm in Python, Java and C++

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.

Applications of Kruskal's algorithm: clustering, mazes, interview problems

  • Clustering: stop when k trees remain, and they are the k clusters whose closest points across clusters lie furthest apart. This is single-linkage clustering.
  • Maze generation: take a grid's walls in random order and remove each one between two cells not yet connected; exactly one path then joins any two cells.
  • Interview problems: LeetCode 1584, Min Cost to Connect All Points, asks for a minimum spanning tree of the complete graph of the points, with Manhattan distances as weights. Kruskal's algorithm solves it, though on a graph this dense, Prim with a plain array is faster.

Six vertices here.
Up to twelve 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.

Four graphs to choose from

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.

Kruskal on a graph you draw

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.

Four stages, six pictures

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).

Python, Java and C++

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.

Quiz

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 and Prim

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.

Lightest edges,
never a cycle.

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