Algorithms and Data Structures · Senior · Question 5 of 75
How do Prim's and Kruskal's algorithms differ?
- ✓Correct answer: Prim grows one tree from a vertex; Kruskal joins forests by cheapest edges
- 2Prim finds shortest paths; Kruskal finds spanning trees
- 3Prim needs sorted edges; Kruskal needs a priority queue of vertices
Explanation
Both compute a minimum spanning tree. Prim adds the cheapest edge leaving the current tree (heap of edges); Kruskal sorts all edges and uses union-find to skip cycles. Kruskal is natural for sparse edge lists, Prim for dense graphs.