cf.completefrontend
GRAPHS · ADVANCED

Kruskal's algorithm (minimum spanning tree)

Connect every node with the lowest total cost by taking edges from cheapest to most expensive and skipping any edge that would close a loop.

Time O(e log e)Space O(n + e)4 practice problemsStep-through picture

The idea

Kruskal's algorithm finds a minimum spanning tree (the cheapest set of edges that connects every node without loops) in a different way from Prim's. Instead of growing one tree, it sorts all edges by cost and looks at them from cheapest to most expensive.

For each edge, it asks: are its two ends already connected by the edges taken so far? If yes, the edge would only close a loop, so skip it. If no, take it, because it joins two separate groups as cheaply as possible.

The "already connected?" question is exactly what union-find answers in almost constant time. The algorithm stops once it has taken n - 1 edges, the size of any spanning tree.

An everyday example

Building bridges between islands on a budget

A group of islands needs bridges so you can drive between any two. You get a price list for every possible bridge and read it from cheapest to most expensive. You build a bridge only if its two islands can't already reach each other through bridges you've built. Each built bridge merges two groups of islands into one. When all islands form one group, you stop.

How the example maps to the code
In the exampleIn the code
The price list, cheapest firstsorted, the edges sorted by weight
Groups of islands joined by bridgesUnion-find groups
Can these two islands already reach each other?find(a) === find(b)
Building a bridgeparent[rootA] = rootB and total += weight
Stopping when everything is one groupused === n - 1

From the slow way to kruskal's algorithm (minimum spanning tree)

  1. Start with the obvious way: try every set of n - 1 edges, keep the ones that connect everything without a loop, and pick the cheapest. Even 20 edges on 10 nodes give 167,960 sets to check, and it grows explosively from there.
  2. Look at the cheapest edge in the whole graph. Splitting the nodes so that its two ends are on different sides, it's the cheapest crossing edge, so by the cut property some cheapest tree contains it. The same thinking works for the next cheapest edge, and the next, as long as the edge joins two pieces that aren't connected yet.
  3. What about an edge whose ends are already connected? Every edge already taken is cheaper or equal, so this edge would close a loop where it's the most expensive member. A cheapest tree never needs that edge. So: go through the edges from cheapest to most expensive, take an edge if it joins two separate pieces, and skip it otherwise.
  4. The only hard question is "are these two ends already connected?". A fresh search each time costs O(n) per edge. Union-find answers it in nearly constant time and merges the two pieces when an edge is taken. Sorting, then one pass with find, stopping at n - 1 edges: that is Kruskal's algorithm.

How it works

  1. Make a union-find parent array where each node is its own group.
  2. Sort a copy of the edges by weight, cheapest first.
  3. Go through the sorted edges. For each [a, b, weight], find the roots rootA and rootB.
  4. If the roots are equal, a and b are already connected: skip the edge.
  5. Otherwise merge the two groups, add weight to total, and count the edge in used.
  6. Stop at n - 1 edges. If fewer were used, the graph isn't connected: return -1.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function kruskalMst(n, edges) {
  2. const parent = Array.from({ length: n }, (_, i) => i);
  3. const find = (x) => {
  4. while (parent[x] !== x) {
  5. parent[x] = parent[parent[x]];
  6. x = parent[x];
  7. }
  8. return x;
  9. };
  10. const sorted = [...edges].sort((a, b) => a[2] - b[2]);
  11. let total = 0;
  12. let used = 0;
  13. for (const [a, b, weight] of sorted) {
  14. const rootA = find(a);
  15. const rootB = find(b);
  16. if (rootA === rootB) continue;
  17. parent[rootA] = rootB;
  18. total += weight;
  19. used++;
  20. if (used === n - 1) break;
  21. }
  22. return used === n - 1 ? total : -1;
  23. }

How fast it is

TimeO(e log e)
Extra memoryO(n + e)

Sorting the e edges is the main cost; each union-find step afterwards is nearly constant time. The sorted copy holds e edges and parent holds n numbers.

  • Best caseO(e)

    The edges are already in weight order, so the sort makes a single pass (V8's sort is TimSort, which notices sorted runs), and the first n - 1 edges form the tree.

  • Average caseO(e log e)

    Edges in random order: sorting dominates, and each find afterwards is nearly constant.

  • Worst caseO(e log e)

    Random order, and the most expensive edge is the only one reaching some node, so the loop reads every edge before it can stop.

Common mistakes

  • Sorting with edges.sort() and no compare function, which sorts as text, so 10 comes before 9.
  • Checking parent[a] === parent[b] instead of comparing roots from find.
  • Forgetting the n - 1 check, and returning a total for a graph in several pieces.
  • Sorting the input array in place when the caller still needs its original order, such as for returning edge indexes.

When to use it

Look for these clues in a problem:

  • The question asks for the cheapest way to connect every node.
  • The input is already a list of edges with costs.
  • You also need to know which edges are in the tree, in cost order.
  • The graph is sparse, so sorting the edges is cheap.

Check yourself

Answer each one in your head first, then open it.

Why is sort((a, b) => a[2] - b[2]) needed instead of sort()?

Plain sort() compares the edges as text, so the order is wrong. The compare function sorts by weight as numbers.

Why can the loop stop at n - 1 edges?

A spanning tree of n nodes has exactly n - 1 edges. Any later edge would close a loop and be skipped anyway.

In the trace, why was 3-4 skipped although it costs only 3?

Nodes 3 and 4 were already connected through 2-3 and 2-4, which cost 1 and 2. Adding 3-4 would close a loop where it's the most expensive edge.

What part of the running time comes from union-find?

Almost none: about two nearly-constant find calls per edge. Sorting the e edges, O(e log e), is the main cost.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Two rules hold after each edge is processed. The edges taken so far are part of some minimum spanning tree T. And the union-find groups are exactly the connected pieces formed by the taken edges.

When an edge a-b is taken, its ends are in different pieces, A and B. Every cheaper edge has already been processed. If some cheaper edge crossed between A and the rest of the graph, its ends were in different groups when it was processed, since groups only grow, so it would have been taken and merged them. So a-b is a cheapest edge leaving A, and the same exchange argument as Prim's applies: if T lacks it, adding it makes a loop that leaves A through another edge at least as expensive, and swapping them keeps T minimal.

When an edge is skipped, its ends already have a path of taken edges, each cheaper or equal. Adding it would only close a loop, and a loop's most expensive edge is never needed. The loop ends after n - 1 taken edges, which connect all n nodes without a loop: a spanning tree inside a minimum spanning tree. If the edges run out first, the graph is in pieces, and it returns -1.

Going deeper

3 more ideas

Why taking the cheapest edge between groups is safe

When Kruskal takes an edge between two groups, every cheaper edge has already been looked at, and none of them connected those groups. So this edge is the cheapest edge crossing between "this group" and "everything else". By the cut property (the same rule behind Prim's algorithm), some minimum spanning tree contains it.

Cost

Sorting takes O(e log e). Each edge then needs two find calls, which are almost constant time with path compression. So sorting is the main cost, and the total is O(e log e).

Ties and the edges you pick

When edges have equal weights, a stable sort keeps their original order, so the tree you build depends on that order. The total cost is always the same. If a problem asks which edges are chosen, it must define a tie rule such as "earlier edges in the input first", which a stable sort follows.

Work it by hand

Every step in a table, with why

Six nodes, nine edges. One edge closes a loop and is skipped, two edges tie at weight 4, and the loop stops before the last three edges.

n = 6, edges = [[0,1,4], [1,2,4], [0,2,6], [2,3,1], [3,4,3], [2,4,2], [4,5,7], [1,5,8], [0,5,5]]

StepEdge (weight)rootArootBtotalusedWhat happensWhy
12-3 (1)2311Take: parent[2] = 3After sorting, the cheapest edge comes first. Its ends are separate, so it's taken.
22-4 (2)3432Take: parent[3] = 4find(2) walks to root 3. Node 4 is alone, so the two pieces merge.
33-4 (3)4432Skip: same rootNodes 3 and 4 are already connected through 2, so this edge would close the loop 2-3-4.
40-1 (4)0173Take: parent[0] = 1A new piece starts on the other side of the graph.
51-2 (4)14114Take: parent[1] = 4This ties with 0-1 at weight 4; the stable sort kept input order. find(2) also shortens a path: parent[2] becomes 4.
60-5 (5)45165Take, then stopfind(0) walks 0 → 1 → 4 and points 0 straight at 4. Now used === n - 1 = 5, so the loop breaks.

It returns 16, using edges 2-3, 2-4, 0-1, 1-2, and 0-5. The edges 0-2 (6), 4-5 (7), and 1-5 (8) are never looked at, because the tree was finished first.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Kruskal's algorithm (minimum spanning tree)O(e log e)O(n + e)The input is a list of edges, the graph is sparse, or you want clusters by stopping early.
Prim's algorithmO(e log e)O(n + e)The graph is given as adjacency lists, or you want the tree grown from one node.
Prim's with an array instead of a heapO(n²)O(n)Every pair of points can be linked, so listing and sorting about n² edges would cost more.

Extra memory: O(n + e): the sorted copy holds e edges, parent holds n numbers, and the sort may use O(e) extra.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Kruskal's algorithm (minimum spanning tree) and the other approaches, on a scale where each line up is 10 times more steps.
  • Kruskal's algorithm (minimum spanning tree), Prim's algorithm O(e log e)
  • Prim's with an array instead of a heap O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Kruskal's algorithm (minimum spanning tree)339,96620 million
Prim's algorithm339,96620 million
Prim's with an array instead of a heap1001 million1 trillion

Inputs that need care

6 tricky inputs
A graph in pieces: n = 5, edges 0-1, 1-2, 3-4
Only 3 edges can be taken, fewer than n - 1 = 4, so it returns -1.
A self-loop like [2, 2, 1]
find(2) equals find(2), so it's skipped like any loop-closing edge.
Two edges between the same pair
The cheaper one comes first and is taken; the other is skipped because its ends now share a root.
Edges with equal weights, like 0-1 and 1-2 at 4
The stable sort keeps their input order. The chosen edges can depend on that order, but total never does.
Negative weights
They sort first and work like any other weight. The cut property doesn't care about signs.
n = 1 with no edges
used stays 0, which equals n - 1, so it returns 0.

Variations and follow-ups

Twists interviewers add

Clustering

To split points into k groups that are as far apart as possible, run Kruskal's and stop after taking n - k edges. The groups in union-find are the clusters, and the next edge that would be taken is the smallest gap between two clusters.

Maximum spanning tree

Sort from most expensive to cheapest instead. The same argument shows the result is the spanning tree with the largest total.

Bottleneck questions

A minimum spanning tree also makes the largest edge on the path between any two nodes as small as possible. So "what's the smallest weight limit that still connects a to b?" is the biggest edge on their path in the tree, or, offline, the weight at which Kruskal's first puts them in one group.

Must-have and never-needed edges

To test whether an edge is in every cheapest tree, run Kruskal's without it: if the total goes up or the graph splits, it's required. To test whether it's in at least one, run Kruskal's with it taken first: if the total stays the same, it can be used.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "minimum cost to connect" when the input is a list of possible connections with prices. Mention that union-find makes the "already connected?" check nearly free.
  • Explain both decisions out loud: "take the edge if it joins two separate pieces, because it's the cheapest way out of its piece; skip it otherwise, because it would be the most expensive edge on a loop".
  • Test by hand a graph with an edge that closes a loop, a tie in weights, and a disconnected graph that must return -1.
  • Expect "Prim's or Kruskal's?". Answer: both are O(e log e). Kruskal's is natural for an edge list and for clustering; Prim's suits adjacency lists and dense graphs, especially the array version.

Where frontend code uses it

The same idea in real UI code
  • Clustering points in a chart or map: run Kruskal and stop early, and the groups left are clusters of nearby points.
  • Maze generators for browser games that join random grid cells with union-find, which is randomized Kruskal's.
  • Planning tools that pick the cheapest set of network links or roads, where the input is naturally a list of possible links with prices.

Related algorithms