Kruskal's algorithm, explained

Kruskal's algorithm finds the same kind of answer as Prim's, a minimum spanning tree, but works in a different way. It does not grow from one node. It looks at all edges from cheapest to most expensive.

For each edge, it asks one question: would adding this edge create a loop? If not, it keeps the edge. If yes, it skips it.

How it works

• Sort all edges by weight, from smallest to largest.
• Take the next edge in the list.
• If it joins two parts that are not yet connected, add it. If both ends are already connected, skip it, because it would form a loop.
• Stop when you have V − 1 edges, or the list ends.

A small example

Take these weighted edges:

A-B:4  A-C:2  B-C:1  B-D:5  C-D:8  D-E:3

Sorted:  B-C 1, A-C 2, D-E 3, A-B 4, B-D 5, C-D 8
Kept:    B-C, A-C, D-E, B-D     (A-B skipped: it would form a loop)
Total weight: 11

Prim's algorithm found a tree with the same total weight.

What to know about its cost

• O(E log E) time, mostly for sorting the edges.
• Uses O(V) space for tracking connected parts.
• Needs an undirected, weighted graph.

Where it works well

• Fast on sparse graphs.
• Easy to explain: cheapest edge first, never make a loop.

Where it struggles

• Needs all edges sorted first.
• Needs a way to check quickly whether two nodes are already connected.

Try it yourself

Open the Graph Algorithms experiment, enter these edges (A-B:4, A-C:2, B-C:1, B-D:5, C-D:8, D-E:3), choose Kruskal's algorithm, and step through it. Then try a different graph and watch how the result changes.

Open the Graph Algorithms experiment