Kruskal vs Prim
Kruskal on sparse graphs, where sorting the edges is cheap. Prim on dense graphs, where there are too many edges to sort and growing outward from one node touches fewer of them.
Both produce a minimum spanning tree, and on a graph with distinct edge weights both produce the same one. They differ in what they iterate over. Kruskal thinks in edges: sort them all and take each one that does not close a cycle, merging a forest into a tree. Prim thinks in nodes: keep one growing tree and repeatedly attach the cheapest edge leaving it.
Side by side
| Dimension | Kruskal | Prim |
|---|---|---|
| Iterates over | Edges, globally sorted | Nodes, expanding a frontier |
| Time | O(E log E), the sort dominates | O(E log V) with a binary heap |
| Data structure | Union-Find | Priority queue |
| Intermediate state | A forest of components | A single connected tree |
| Best on | Sparse graphs | Dense graphs |
| Disconnected graphs | Yields a spanning forest naturally | Only spans the component it starts in |
| Dense optimum | No better variant | O(V squared) without a heap, which wins when E approaches V squared |
When to pick each
Kruskal
- The graph is sparse, so sorting E edges is inexpensive.
- The edges arrive as a list already, with no adjacency structure built.
- The graph may be disconnected and a spanning forest is acceptable.
Prim
- The graph is dense, where E approaches V squared and sorting every edge is wasteful.
- You already have an adjacency list and want to avoid materialising an edge list.
- You want the intermediate state to always be a connected tree, which some incremental applications need.
Assuming the minimum spanning tree is unique. It is only guaranteed unique when all edge weights are distinct. With ties, Kruskal and Prim can return different trees of the same total weight, and a test comparing your edge list to an expected one will fail even though your answer is correct. Compare total weights, not edge sets.
Questions people ask
Do they always give the same tree?
Only when every edge weight is distinct. With ties there can be several minimum spanning trees, all of equal total weight, and the two algorithms may pick different ones.
Why does Kruskal need Union-Find?
To answer whether an edge would close a cycle, which is the same as asking whether its two endpoints are already connected. Union-Find answers that in near-constant time, and without it the check would be a graph search per edge.
Is a minimum spanning tree the same as shortest paths?
No, and conflating them is a common error. An MST minimises total edge weight across the whole tree; it does not minimise the distance between any particular pair of nodes. The path between two nodes in an MST can be much longer than their shortest path.