What is the difference between Kruskal's and Prim's? When is one preferred?

Difficulty: 5/10

minimum spanning tree, graph algorithms, algorithm complexity

Kruskal vs Prim

Kruskal is edge-centric: it globally sorts edges and builds multiple components that eventually merge into an MST. Prim is vertex/tree-centric: it grows one tree outward from a starting vertex. Kruskal is especially natural for edge lists and sparse graphs, while Prim is often convenient with adjacency structures and dense graphs.

javascript

1
Kruskal uses Union-Find.
2
Prim typically uses a priority queue.
3
Kruskal complexity: O(E log E).
4
Prim with binary heap: O(E log V).
5
Both produce an MST for a connected weighted undirected graph.

Scenario Questions

0-2 years experience

2-5 years experience

Follow-up Questions