Kruskal's or Prim's: which MST algorithm fits a sparse edge-weighted graph, and why?
answer
- One sorts edges, one grows a tree
- What dominates each algorithm's running time?
- Compare E log V against V squared
- Which Prim variant drops the priority queue?
- Dense means E approaches V squared
basics
~20 sOn a sparse graph both cost about O(E log V), and Kruskal's is the simpler fit: sort the edges, reject the cycle-closing ones cheaply. Prim's wins on dense graphs, where its scan-based form runs in O(V^2).
solid answer
~50 sKruskal's sorts all `E` edges by weight and walks them cheapest-first, accepting an edge whenever its two endpoints are still in different components — a disjoint-set structure answers that in near-constant amortized time. Cost is `O(E log E)`, which is `O(E log V)` since `E` is at most `V^2`; the sort dominates. Prim's instead grows one connected tree from an arbitrary start node, repeatedly pulling the cheapest edge leaving the tree out of a priority queue: `O((V+E) log V)` with a binary heap. On a sparse trench-cost graph — a few candidate cables per office — the two are asymptotically equivalent and Kruskal's is easier to reason about, especially if the edges arrive already sorted by price. On a dense graph where `E` approaches `V^2`, Prim's with a plain array scan instead of a heap is `O(V^2)` and beats the `O(V^2 log V)` sort.
go deeper
Know that both algorithms produce a minimum spanning tree and that one sorts all edges while the other grows a single tree from a start node.
Explain the dominant cost of each — the edge sort versus the priority-queue operations — and state which graph density favours which, naming the Prim variant you mean.
Justify a pick from the real input shape: how the edge data arrives, whether it fits in memory, whether an early exit or a pre-sorted stream applies, and how much the constant factors matter at your actual size.
Weigh the asymptotics against maintainability and data flow — the simpler algorithm your team can debug at 3 a.m. often beats the one that wins on paper at a size you will never reach.
## Two greedy strategies, one guarantee Both algorithms are greedy and both are correct for the same reason: each step adds an edge that is provably safe (the cheapest edge crossing some partition of the nodes). They differ entirely in *which* partition they look at, and that choice drives the data structures and the cost. **Kruskal's — sort globally, join components.** Sort every edge by weight ascending. Walk the sorted list; for each edge, ask whether its endpoints already sit in the same component. If yes, taking it would close a cycle, so skip it. If no, accept it and merge the two components. Stop after `V-1` accepted edges. The intermediate state is a *forest* — many disconnected fragments that gradually merge. **Prim's — grow one tree.** Pick any start node. Maintain the set of nodes already in the tree and a priority queue of candidate edges leaving that set. Repeatedly extract the cheapest such edge; if it leads somewhere new, add that node and push its incident edges. The intermediate state is always a *single connected tree*. Both end at a tree of total minimum weight. On a graph with distinct weights they end at the *same* tree; with ties they may pick different equally-minimal edge sets. ## The cost model | Variant | Time | Dominated by | |---|---|---| | Kruskal's, comparison sort + disjoint sets | `O(E log E)` = `O(E log V)` | the edge sort | | Prim's, binary heap + adjacency lists | `O((V+E) log V)` | heap operations | | Prim's, plain array scan + adjacency matrix | `O(V^2)` | scanning for the cheapest frontier node | | Prim's, Fibonacci heap | `O(E + V log V)` | mostly theoretical interest | `log E` and `log V` are within a constant factor of each other because `E <= V^2` implies `log E <= 2 log V` — which is why Kruskal's is quoted either way. **Sparse** (`E` proportional to `V`, e.g. each office has three or four candidate trench routes): Kruskal's is roughly `O(V log V)`, heap-based Prim's is roughly `O(V log V)`. A wash asymptotically. Pick on secondary grounds: are the edges already sorted or streamable in price order? Do you already have a disjoint-set structure? Kruskal's is the shorter code and the easier one to explain in a review. **Dense** (`E` proportional to `V^2`, e.g. every office can reach every other): Kruskal's pays `O(V^2 log V)` just to sort. Prim's scan-based form pays `O(V^2)` with tiny constants and no auxiliary structures at all. That extra `log V` factor is the whole reason the dense case has a different default. ## What changes in practice, not just in the exponent - **Early exit.** Kruskal's can stop the moment it has accepted `V-1` edges; on a graph where the cheap edges happen to span everything, much of the sorted tail is never examined. If you sort lazily — say, by pulling edges from a priority queue instead of fully sorting — the expected work drops further. The worst case does not improve. - **Streaming input.** If trench-cost edges arrive from a pricing service already ordered cheapest-first, Kruskal's needs no sort at all and becomes near-linear in `E` times the disjoint-set cost. Prim's cannot exploit that ordering, because it only ever cares about edges touching the current tree. - **Locality.** Prim's touches only edges incident to the growing tree, which is friendly if the graph is stored as adjacency lists and you cannot afford to materialize all `E` edges at once. Kruskal's wants the full edge list in memory to sort it. - **Start node is irrelevant to the answer.** Prim's from any start node produces a tree of the same minimum total weight on a connected graph. Candidates sometimes claim you should start at the highest-degree node or at an endpoint of the globally cheapest edge; neither affects correctness or the total. ## Precision traps in the complexity story Be careful with the directions here, because interviewers pick at them: - The disjoint-set cost is **amortized near-constant** (inverse-Ackermann), not strictly `O(1)`. It is never the dominant term in Kruskal's, but do not upgrade it to constant time in your answer. - `O(E log E)` is an **upper bound**. It does not say the algorithm exhibits that behavior on your inputs; with early exit and mostly-sorted price data, real runs sit well below it. - Asymptotic superiority says nothing at small `n`. For a few dozen offices, both algorithms finish instantly, and the deciding factors are which one your team can maintain and which one the input format suits — not the exponent. - "Prim's is faster on dense graphs" is true only for the **array-scan** variant. Heap-based Prim's on a dense graph is `O(V^2 log V)`, no better than Kruskal's. Naming the variant is what separates a memorized answer from an understood one.
- Does the choice of Prim's starting node change the resulting tree?It can change which edge set you get when weights tie, but never the total weight: on a connected graph every start node yields a tree of the same minimum total. There is no advantage to starting at a high-degree node or at an endpoint of the cheapest edge, and claiming otherwise is a common tell that someone memorized the algorithm without understanding the greedy argument.
- Trench prices already arrive sorted cheapest-first from a pricing service — how does that change your pick?It strongly favours Kruskal's, whose dominant cost is exactly the sort you no longer have to pay. The remaining work is one pass over the edges with near-constant amortized component queries, so the algorithm becomes essentially linear in the number of candidate links. Prim's cannot use that ordering, since it only considers edges touching the tree it has grown so far.
- Can Kruskal's stop before it has examined every edge?Yes — once V-1 edges have been accepted, the tree spans every node and the rest of the sorted list is irrelevant. That early exit helps whenever the cheap end of the price range already connects everything, and it pairs well with sorting lazily rather than fully up front. It does not improve the worst case, where the last accepted edge sits near the end of the order.
saying these in an interview costs you the question
- Says Prim's is always faster than Kruskal's
- Quotes Prim's as O(V^2) without naming the array-scan variant
- Calls the disjoint-set component check strictly O(1)
- Thinks the start node changes the minimum total weight
- Claims the two algorithms can produce different total weights