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

Updated 11 Nov 20266 min read
MST and Prim's Algorithm Interview Questions: Model Answers and Worked Traces

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 A, weight 0

{A}

B=4(A), C=3(A), D=infinity, E=infinity, F=infinity

0

1

C through A-C=3

{A,C}

B=1(C), D=4(C), E=5(C), F=infinity

3

2

B through C-B=1

{A,B,C}

D=2(B), E=5(C), F=infinity

4

3

D through B-D=2

{A,B,C,D}

E=2(D), F=3(D)

6

4

E through D-E=2

{A,B,C,D,E}

F=3(D)

8

5

F through D-F=3

{A,B,C,D,E,F}

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.

Six-vertex weighted graph with orange MST edges A-C 3, C-B 1, B-D 2, D-E 2 and D-F 3; extraction order A, C, B, D, E, F and total weight 11.

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.

Cut-property diagram separates A, B, C from D, E, F; B-D=2 is the light crossing edge, followed by D-E=2 after D joins.

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

O(E log V) with adjacency list and binary heap

O(E log E), also O(E log V) for a simple graph

Disconnected input

One run covers one component

Produces a minimum spanning forest

Representation trade-off

Matrix gives O(V^2)

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:

  1. Set all keys to infinity and parents to null. Set the start key to 0; push it.

  2. Pop the smallest entry. Skip it when its vertex is finalised or its key is stale.

  3. Otherwise finalise it and add its key to the total, except at the root.

  4. For every (u,v,w), if v is outside and w < 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 U-V=-2, V-W=1, U-W=4, choose them: -2+1=-1.

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.