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

Updated 13 Nov 20266 min read
Prim's Algorithm and Minimum Spanning Tree: Worked Example, Complexity and Exam Traps

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.

Code
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] = u

An 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

{A}

B: infinity to 4 via A; C: infinity to 3 via A; D,E,F remain infinity

C, key 3

AC(3)

{A,C}

B: 4 to 1 via C; D: infinity to 4 via C; E: infinity to 2 via C

B, key 1

CB(1)

{A,B,C}

D: 4 to 2 via B

D, key 2

BD(2)

{A,B,C,D}

F: infinity to 2 via D

E, key 2

CE(2)

{A,B,C,D,E}

EF=3 does not improve F=2 via D

F, key 2

DF(2)

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

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.

Six-vertex weighted graph with the Prim MST edges AC, CB, BD, CE and DF in green, numbered in extraction order, totalling 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.

Five-panel cut-property trace showing the tree set S growing from A, with chosen crossing edges AC, CB, BD, CE, DF summing to 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 V-1 edges selected

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:

  1. Confirm that the input is connected and undirected.

  2. Set one start key to 0 and all others to infinity.

  3. Repeatedly take the minimum-key vertex outside the tree.

  4. Update only direct crossing-edge keys.

  5. Stop after V-1 chosen 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.