DSA interview question

Prim's Algorithm (MST Weight)

Hard · Data structures · Topics: graph, mst, greedy, priority queue

The problem

A city must lay water pipes to connect all V districts at minimum total cost, given possible pipe routes with costs: an MST. Prim's algorithm grows one tree from district 0. At every step it adds the cheapest edge leaving the tree, found with a min-heap, until every district is included. The cut property guarantees that each such edge belongs to some MST.

Example: 3 districts, routes 0-1 (5), 1-2 (3), 0-2 (1) → 4.

Function signature

long long spanningTree(int V, const vector<array<int, 3>>& edges);  // connected, undirected

Test cases

Input `(V, edges)`	Output	Explanation
`(3, [[0,1,5],[1,2,3],[0,2,1]])`	`4`	0-2 and 2-1
`(5, [[0,1,2],[0,3,6],[1,2,3],[1,3,8],[1,4,5],[2,4,7],[3,4,9]])`	`16`	2 + 3 + 5 + 6
`(4, [[0,1,1],[1,2,2],[2,3,1],[0,3,4],[0,2,3]])`	`4`
`(2, [[0,1,5]])`	`5`
`(1, [])`	`0`

(Confirm: the graph is connected and undirected; parallel edges may exist, and only the cheapest matters.)

How interviewers phrase it

"Given a weighted, undirected, connected graph, find the sum of the weights of the edges of a minimum spanning tree" (GeeksforGeeks "Minimum Spanning Tree"), using Prim's algorithm.

Clarifying questions to ask

Is the graph connected? (Yes.)
Do I need the weight or the edges? (The weight; tracking parents gives the edges.)
Dense or sparse? (That decides between the heap version and the O(V²) array version.)

Follow-ups to expect

"Why is the cheapest edge leaving the tree safe?"
"Why can popped entries be stale?"
"Prim vs Kruskal?"
"O(V²) version?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview