DSA, Database System & Operating System — Sorting, Searching, and Graphs, NEC licence examination syllabus (Nepal Engineering Council).
Minimum Spanning Trees: connecting everything as cheaply as possible
Both algorithms below are "greedy" — always taking the locally cheapest option — yet BOTH provably find the globally optimal answer.
A Minimum Spanning Tree (MST) connects all vertices in a weighted graph using the minimum possible total edge weight, with no cycles — think laying the cheapest possible network of cables to connect every city, using as little total cable as possible.
🌳 Prim's vs Kruskal's
Prim'sGrow ONE tree outward — always add the cheapest edge that connects the current tree to a NEW vertex not yet included.
Kruskal'sConsider ALL edges sorted by weight, adding each one as long as it doesn't create a cycle — the tree can grow in multiple disconnected pieces before finally merging.
Worked example — Kruskal's on edges (weight): AB(1), BC(3), AC(2), CD(4)
Sort by weight: AB(1), AC(2), BC(3), CD(4)
Add AB(1) → no cycle, keep. Total: 1
Add AC(2) → no cycle, keep. Total: 3
Add BC(3) → WOULD create cycle A-B-C-A, SKIP
Add CD(4) → no cycle, keep. Total: 7
Final MST edges: AB, AC, CD — total weight 7
💡 Practice both Prim's and Kruskal's on the SAME small weighted graph (5-6 vertices) — both should arrive at the same total MST weight, even if they pick a different valid set of edges along the way.
Both algorithms on the same graph
Take five vertices with these edges: A–B 4, A–C 1, B–C 2, B–D 5, C–D 8, C–E 10, D–E 3.
KRUSKAL — sort all edges by weight, take each unless it makes a cycle
A–C (1) take total 1
B–C (2) take total 3
D–E (3) take total 6
A–B (4) SKIP A and B are already connected via C
B–D (5) take total 11
C–D (8) SKIP cycle
C–E (10) SKIP cycle
MST edges: A–C, B–C, D–E, B–D TOTAL = 11
PRIM — start at A, always take the cheapest edge leaving the tree
tree {A} cheapest out is A–C (1) total 1
tree {A,C} cheapest out is C–B (2) total 3
tree {A,B,C} cheapest out is B–D (5) total 8
tree {A,B,C,D} cheapest out is D–E (3) total 11
MST edges: A–C, C–B, B–D, D–E TOTAL = 11
The same total by a different route. Kruskal took D–E third, when the tree was still in two disconnected pieces; Prim could not take it until D had joined. Both are optimal — the edge order differs, the total never does.
💡 Note that both produced 4 edges for 5 vertices. A spanning tree of n vertices always has exactly n−1 edges — a free check on any exam answer. More means a cycle; fewer means it is not connected.
How each one avoids cycles
🔍 The cycle test is the real difference
PrimCannot create a cycle by construction — it only ever adds an edge to a vertex not yet in the tree, so no test is needed.
KruskalAdds edges anywhere, so it must ask "are these two already connected?" — answered with a union-find structure.
That difference decides which to use. Kruskal sorts every edge, costing O(E log E), which suits sparse graphs. Prim with a heap costs O(E log V) and, in its simple array form, O(V²) — which is better on dense graphs where E approaches V².
💡 If edge weights are all distinct the MST is unique, so both algorithms return exactly the same edge set. With ties there can be several equally-minimal trees, and the two algorithms may legitimately return different ones — which is why an exam answer should state the total, since that is what is uniquely determined.
Why greedy works here
Greedy algorithms usually fail to find global optima. MST is one of the cases where it provably succeeds, and the reason is worth a sentence.
The cut property: for any way of splitting the vertices into two groups, the cheapest edge crossing that split must be in some MST. Both algorithms only ever add such an edge — Prim across the boundary of its tree, Kruskal across the split its union-find structure represents — so neither can make a choice it later regrets.
Syllabus points
Prim's algorithm
Kruskal's algorithm
Round-Robin algorithm
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.