MST and Prim's Algorithm Interview Questions: Model Answers and Worked Traces
Build an interview-ready understanding of minimum spanning trees and Prim's algorithm through an exact trace, correctness proof, Kruskal comparison and edge-case checks.
KnowledgeGate Team
Exam prep & CS education

A strong MST answer names the invariant, traces the heap, and explains why the chosen edge is safe. The six-vertex example below computes the tree weight, then the comparison, implementation checks, and edge cases turn that reasoning into interview answers.
1. MST interview foundations in a 60-second answer
What is a spanning tree? For a connected, undirected graph G=(V,E), it spans every vertex, is connected and acyclic, and has exactly |V|-1 edges. A tree edge is selected; a non-tree edge is not.
What is an MST? It minimises the sum of selected tree-edge weights, not distances from one source. Negative and zero weights remain valid because MST reasoning compares edges, not path distances.
What input does Prim require? A weighted, undirected graph. A disconnected graph has no single MST, though it can have a minimum spanning forest.
A cut (S, V-S) separates vertices. A crossing edge joins its sides, and a light edge has minimum crossing weight. An interview answer can move from the definition to the trace and complexity; a deeper follow-up asks for invariants, proof, and edge cases.
2. Prim's algorithm, invariant and data structures
How does Prim's algorithm work? Start anywhere and maintain the set S already in the tree. For each outside vertex v, key[v] is its cheapest edge to S, while parent[v] records that edge's inside endpoint. Repeatedly finalise the outside vertex with minimum key, add its parent edge, then relax its incident edges.
The selected edges form one acyclic tree on S. Before each extraction, every outside key is the cheapest known crossing edge from S. The next minimum-key edge is safe by the cut property. It is not the globally smallest unused edge, which is Kruskal's rule.
An adjacency list and binary heap store (key, vertex, parent) entries. With a matrix, scan outside vertices for the next key. With correct code, the start may change the returned MST when several exist, not its optimal weight.
3. Prim's algorithm worked trace on six vertices
Use vertices A, B, C, D, E, F and edges A-B=4, A-C=3, B-C=1, B-D=2, C-D=4, C-E=5, D-E=2, D-F=3, E-F=6. Start at A. Infinity means that no crossing edge to that outside vertex has been discovered yet.
Iteration | Vertex finalised through edge | S after extraction | Outside keys with parents | Running MST weight |
|---|---|---|---|---|
Start | Root |
|
| 0 |
1 |
|
|
| 3 |
2 |
|
|
| 4 |
3 |
|
|
| 6 |
4 |
|
|
| 8 |
5 |
|
| None | 11 |
What MST does the trace return? It selects {A-C=3, C-B=1, B-D=2, D-E=2, D-F=3}. That is 6-1=5 edges, and 3+1+2+2+3=11. The accumulated 11 is the total tree weight, not one vertex's key or a source-to-vertex path length.

4. Why Prim's greedy edge is safe
Why is Prim correct? The cut property says that for any cut respecting the already selected edges, a light crossing edge is safe. By induction, choose an MST T containing every already selected edge. If T lacks Prim's edge e, adding e creates a cycle containing an edge f that crosses the same cut. No selected edge crosses a respecting cut, so f is not among the prior choices. Since w(e) <= w(f), the tree T-f+e contains all prior choices plus e, and its weight cannot exceed that of T; it is therefore also an MST.
At S={A,B,C}, the crossing values are B-D=2, C-D=4, C-E=5; B-D is uniquely light. After D joins, they are D-E=2, D-F=3, C-E=5; D-E is safe next.

Prim's heap invariant and exchange proof answer the interview angle. For GATE numericals that compare Kruskal and Prim and test uniqueness on a five-vertex graph, study Minimum Spanning Tree GATE: Kruskal, Prim and Uniqueness after explaining this exchange argument.
5. Prim versus Kruskal: model comparison answer
Point | Prim | Kruskal |
|---|---|---|
Greedy choice | Cheapest edge crossing its tree | Cheapest edge joining different components |
Shape while running | One growing tree | A merging forest |
Main data structures | Keys plus heap, or matrix scan | Sorted edges plus disjoint-set union |
Typical complexity |
|
|
Disconnected input | One run covers one component | Produces a minimum spanning forest |
Representation trade-off | Matrix gives | Edge-list sorting is natural |
Matrix Prim can suit dense graphs, but neither algorithm is always better without specifying representation and implementation.
Kruskal accepts B-C=1, B-D=2, D-E=2, A-C=3, D-F=3, then stops. Its total is 1+2+2+3+3=11, matching Prim. Both are greedy, but safety depends on the problem's invariant. Greedy Algorithms: Huffman, Knapsack, Activity Selection develops this distinction.
6. Prim implementation, complexity and debugging follow-ups
How would you code Prim safely? Follow this language-neutral sequence:
Set all keys to infinity and parents to null. Set the start key to
0; push it.Pop the smallest entry. Skip it when its vertex is finalised or its key is stale.
Otherwise finalise it and add its key to the total, except at the root.
For every
(u,v,w), ifvis outside andw < key[v], update key and parent; push a fresh entry. Repeat while the heap has entries.
Inspecting edges from their endpoints with logarithmic heap updates gives O(E log V) time and O(V+E) space. Matrix Prim takes O(V^2) time and storage. Use a 64-bit or wider total if needed.
What changes for a disconnected graph? Report no MST if vertices remain unvisited. For a forest, restart at each one. With P-Q=1, R-S=2, forest {P-Q, R-S} has two components and total 1+2=3.
Avoid adding weight during relaxation, accepting stale entries twice, using path sums as keys, losing parent edges, or returning an invalid set with the right total.
7. MST edge cases, tie handling and interview practice
Question | Model answer | Exact check |
|---|---|---|
Do negative weights break Prim? | No. The cut property compares weights. | For |
Do equal weights prove multiple MSTs? | No. Distinct weights guarantee uniqueness; repeats alone do not. | Seek distinct safe sets with the same minimum. |
For P-Q=1, P-R=1, Q-R=1, Q-S=2, R-S=2, two triangle edges plus one weight-2 edge span all vertices for 1+1+2=4. Prim's ties may return different valid trees. Every main-graph choice is uniquely lightest, so no alternative exists.
Prim does not solve directed MST problems. Self-loops cannot help a spanning tree; use the cheapest eligible parallel edge. A connected V-vertex graph returns V-1 edges.
KnowledgeGate has over 60 MST and Prim's Algorithm questions for practice. For wider patterns, use DSA Interview Questions: 7 Patterns for Placements, then Resume & Interview Preparation.
8. The short version and next coding step
Recall: connected weighted undirected graph -> grow one tree -> choose the lightest crossing edge -> justify it by the cut property -> update keys -> stop after V-1 edges. The trace returns {A-C, C-B, B-D, D-E, D-F}, total 11, in O(E log V) heap time.
Redraw the trace, explain the exchange proof aloud, then implement connected-MST and forest behaviours. Coding for Placements offers a broader multi-language practice route.
Keep learning
Prim's Algorithm and Minimum Spanning Tree: Worked Example, Complexity and Exam Traps
Learn what makes Prim's greedy choice safe, trace every key update on a six-vertex graph, and avoid the mistakes that derail MST questions.
Kruskal's Algorithm Interview Questions: MST Traces, DSU and Model Answers
Trace Kruskal's algorithm on a six-vertex graph, then rehearse model answers on DSU, correctness, complexity, ties, negative weights and disconnected inputs.
Prim's Algorithm MCQs: 12 Solved MST Questions with Explanations
Solve 12 Prim's algorithm and minimum spanning tree questions, then check each answer against a concise explanation, one full trace and two diagrams.
Minimum Spanning Tree for GATE: Kruskal and Prim Numericals with Unique-MST Questions
Run Kruskal and Prim on the same weighted graph, verify their common cost, and use cut, cycle, and equal-weight reasoning to answer uniqueness questions.





