3.5Minimum spanning trees
The idea
A minimum spanning tree connects every vertex with the cheapest total weight and no cycle.
Think of it like this: Laying cable between towns using the least total cable.
Why it exists
Kruskal and Prim questions appear almost every year: edge order, total weight, uniqueness.
How it works
- Kruskal: sort edges, add the next one if it joins two components.
- Prim: from a start vertex, repeatedly add the cheapest edge leaving the tree.
- Both give a tree with V − 1 edges.
- Distinct weights mean a unique MST.
Worked example: The sample graph
Both algorithms give a total weight of 18. Kruskal takes weights 1, 2, 3, 3, 4, 5 and skips the second weight-4 edge (D–E) because D and E are already connected.
Now play with it
- →Run Kruskal and see skipped (dashed) edges.
- →Run Prim and compare the order in which edges are added.
Yellow = waiting, white fill = current, green = finished. Thick green edges are tree / MST edges.
- sort edges by weight: EF(1) AD(2) BE(3) FG(3) AB(4) DE(4) CF(5) BC(6) DG(8) EG(9)
- take EF (1): joins two different components
- take AD (2): joins two different components
- take BE (3): joins two different components
- take FG (3): joins two different components
- take AB (4): joins two different components
- skip DE (4): both ends already connected, it would make a cycle
- take CF (5): joins two different components
Sorts edges and adds each one that joins two components (union-find). O(E log E) = O(E log V).
Yellow = waiting, white fill = current, green = finished. Thick green edges are tree / MST edges.
- add A to the tree (start)
- B is now reachable with key 4 via A
- D is now reachable with key 2 via A
- add D to the tree using the cheapest crossing edge (weight 2)
- E is now reachable with key 4 via D
- G is now reachable with key 8 via D
- add B to the tree using the cheapest crossing edge (weight 4)
- C is now reachable with key 6 via B
- E is now reachable with key 3 via B
- add E to the tree using the cheapest crossing edge (weight 3)
- F is now reachable with key 1 via E
- add F to the tree using the cheapest crossing edge (weight 1)
- C is now reachable with key 5 via F
- G is now reachable with key 3 via F
- add G to the tree using the cheapest crossing edge (weight 3)
- add C to the tree using the cheapest crossing edge (weight 5)
Grows one tree by always adding the cheapest edge leaving it. O(E log V) with a heap.
Check yourself
If all edge weights of a connected graph are distinct, its MST is
Exam notes (the dense version)
An MST connects all V vertices with V − 1 edges of least total weight. Kruskal: sort edges, add each edge that does not form a cycle (union-find), O(E log E). Prim: grow one tree by adding the cheapest edge leaving it, O(E log V) with a binary heap, O(V²) with an array. The cut property: the lightest edge crossing any cut is in some MST. If all edge weights are distinct the MST is unique.
Previous year questions: Graph Algorithms (35)
PYQs are grouped by topic, so this is the full set for Graph Algorithms; try the ones that match this subtopic. Open all 35 on the topic page.