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.
KnowledgeGate Team
Exam prep & CS education

Prim's algorithm is often memorised as "take the cheapest edge", but the edge must cross from the current tree to an unvisited vertex. Otherwise it may create a cycle. On the six-vertex graph below, AC(3), CB(1), BD(2), CE(2), and DF(2) form an MST with total weight 10. Prim's algorithm belongs in the graph-algorithm portion of GATE CS preparation.
Minimum spanning tree basics before Prim's algorithm
An undirected weighted graph has edges that work in both directions, with a numerical weight on each edge. A spanning tree includes every vertex, remains connected, contains no cycle, and has exactly |V| - 1 edges. A minimum spanning tree, or MST, is the spanning tree whose edge weights have the smallest possible sum. Every spanning tree has the same number of edges, so an MST minimises weight, not edge count.
A single MST requires a connected, undirected graph. A disconnected graph instead has a minimum spanning forest. Negative and zero weights are valid. Equal weights may allow several MSTs, but equality alone does not prove that several exist.
If traversal terminology feels unfamiliar, revise graph traversal and shortest-path basics first. A shortest-path tree minimises distances from one source. An MST minimises the total tree weight. One cannot replace the other.
Why Prim's greedy choice is safe: the cut property
A cut partitions the vertices into (S, V - S). During Prim's algorithm, S contains the vertices already in the growing tree. A legal next edge has one endpoint in S and the other outside it. An edge with both endpoints in S is rejected because it would create a cycle. The selected edge is a lightest edge crossing the cut.
Why is that safe? Suppose an MST does not contain the selected light crossing edge. Adding that edge creates a cycle. That cycle must contain another edge crossing the same cut. Remove that other crossing edge, and the graph is again a spanning tree with no greater cost. Therefore some MST agrees with the greedy choice. The cut, cycle and graph terminology behind this argument is worth knowing. Prim guarantees minimum total weight, not a unique edge set when ties exist.
Prim's algorithm mechanics and pseudocode
For every vertex v, key[v] stores the lightest direct edge currently known from the tree to v. parent[v] stores that edge's tree endpoint, and inMST[v] records whether v has been extracted.
key[start] = 0; every other key = infinity
parent[*] = none; inMST[*] = false
push (0, start) into a min-priority queue
while fewer than |V| vertices have been extracted:
extract an unvisited u with minimum key
if key[u] is infinity: report disconnected input
mark u inMST
if u is not start: add (parent[u], u) to the answer
for each edge (u, v, w), where v is outside the tree:
if w < key[v]: set key[v] = w and parent[v] = uAn answer edge enters only when its outside vertex is extracted. Choosing the globally lightest unused edge is Kruskal-like. Adding weights from the start is Dijkstra-like. Prim keeps only the cheapest direct connection from each outside vertex to the current tree.
Fully worked Prim's example from start vertex A
Use the connected undirected graph V = {A, B, C, D, E, F} with exactly these edges: AB=4, AC=3, BC=1, BD=2, CD=4, CE=2, DE=3, DF=2, EF=3. Start at A. If two keys tie, extract alphabetically for this trace only. That tie-break makes the trace deterministic, but it is not part of Prim's correctness condition.
Extracted vertex | Edge added | Tree vertices | Changed keys |
|---|---|---|---|
A, key 0 | None, start |
|
|
C, key 3 |
|
|
|
B, key 1 |
|
|
|
D, key 2 |
|
|
|
E, key 2 |
|
|
|
F, key 2 |
|
| None |
After extracting C, its edge BC=1 reduces B from 4 to 1. After extracting B, BD=2 reduces D from 4 to 2. At that point D and E tie at 2, so the trace takes D. Then E and F tie at 2, so it takes E.
The MST edge set is {AC(3), CB(1), BD(2), CE(2), DF(2)}. It has 5 = |V| - 1 edges, and its total is 3 + 1 + 2 + 2 + 2 = 10.

Prove and independently check the worked MST
Read the trace as a sequence of cuts. From {A}, choose AC=3 over AB=4. From {A,C}, choose CB=1. From {A,B,C}, both BD=2 and CE=2 are legal light choices, and the alphabetical rule leads to BD. From {A,B,C,D}, CE=2 and DF=2 tie, so take CE. Finally, DF=2 is the lightest connection to F. Both tied weight-2 edges are eventually needed in this trace, so a tied extraction does not itself prove that several MSTs exist.
Now check independently with Kruskal's method. Sort edges by weight and accept BC=1, BD=2, CE=2, and DF=2; these create no cycle. The next accepted edge is AC=3, which connects A. The same five edges appear, and the independent sum is again 1 + 2 + 2 + 2 + 3 = 10.

Time complexity, space, and representation choices
With an adjacency matrix and a linear scan to find the next minimum key, Prim takes O(V^2) time. This simple form can suit dense graphs. The matrix occupies O(V^2) storage, while the key, parent, and visited arrays need O(V) auxiliary space.
With an adjacency list and binary min-heap, the time is O((V+E) log V), commonly written O(E log V) for a connected graph. Graph storage is O(V+E), and the algorithm arrays use O(V). A lazy heap may hold several entries for one vertex after key decreases, so skip an entry if its vertex was already extracted.
The worked graph has V=6 and E=9, small enough for a hand trace. As graphs grow, density determines which representation is more sensible.
Prim's algorithm traps and exam-style questions
Trap | Correction |
|---|---|
Edge internal to the current tree | Reject it because it creates a cycle. |
Full path sum used as a key | Store only the direct crossing-edge weight. |
Globally lightest edge chosen without one growing tree | This is Kruskal-like. |
Fewer than | The graph remains unspanned. |
Directed or disconnected input | Ordinary MST preconditions fail. |
New start assumed to change minimum cost | Order or a tied tree may change, but minimum cost does not. |
Questions can ask for the next extraction, final MST weight, edge membership through cut or cycle reasoning, or the correct matrix versus heap complexity.
If AB falls from 4 to 2, rerun the cut decisions. Subtracting 2 from the old total ignores whether the changed edge enters the MST.
For timed application, use the GATE Test Series. The KnowledgeGate practice bank has 50+ questions currently available under the MST and Prim's algorithm subtopic for focused practice.
Prim's algorithm in the short version and the next step
Keep this five-line checklist:
Confirm that the input is connected and undirected.
Set one start key to 0 and all others to infinity.
Repeatedly take the minimum-key vertex outside the tree.
Update only direct crossing-edge keys.
Stop after
V-1chosen edges and sum them.
For this graph, the MST weight is 10. Redraw it, rerun Prim from F, and verify that the minimum total stays 10 even if the extraction order changes. Then use the structured GATE CS concept and practice route to connect this trace with the rest of graph theory.
Keep learning
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.
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.
Minimum Spanning Trees: Kruskal, Prim, Cut Property, and Worked Examples for GATE CS
Build MST intuition from first principles, trace Kruskal and Prim on the same graph, count tied MSTs, and avoid common GATE CS traps.
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.





