Kruskal vs Prim

Kruskal's algorithm and Prim's algorithm both find a minimum spanning tree, and the choice between them comes down to how the graph is stored and how many edges it has. This card sets out what they share, where they differ, and a rule for picking one.

Both are greedy: each adds one edge at a time and never takes one back. Both are correct for the same reason, the cut property from Minimum Spanning Trees and the Cut Property, applied to a different cut at each step. On the topic's graph both found the tree A-C, B-C, B-D, D-E, E-F with total 17, and when no two weights are equal they always find the same tree, because there is only one. They differ in what they grow, what they need, and what they cost.

The two heap-based times are closer than they look. E is at most V², so log E is at most 2 log V, and O(E log E) is the same class as O(E log V). What separates them in practice is the input: Kruskal's algorithm has to see every edge before it starts, while Prim's works outward from what it has. On a dense graph, where E is close to V², Prim's algorithm with a plain scan of best edges runs in O(V²) and beats both heap versions, since it never sorts or pushes an edge at all.

The rule: use Kruskal's algorithm when the edges come as a list or the graph is sparse, and when a forest is an acceptable answer; use Prim's algorithm when the graph is dense, stored as neighbours or a matrix, or when the tree must grow from a given vertex.