Comparing MST Algorithms (Edexcel A-Level Further Mathematics): Revision Notes

10.3.4 Comparing MST Algorithms

Introduction to the Minimum Spanning Tree Problem

A minimum spanning tree (MST) is a subset of edges in a connected, weighted graph that connects all vertices with the minimum possible total weight and no cycles. MSTs are widely used in network design, such as optimising electrical grids, communication networks, or road systems.

Two key algorithms for solving MST problems are Prim's Algorithm and Kruskal's Algorithm.

Comparison: Prim vs. Kruskal

Aspect	Prim's Algorithm	Kruskal's Algorithm
Approach	Grows a connected MST from a single vertex.	Adds smallest edges, ensuring no cycles.
Graph Representation	Works well with adjacency matrices.	Works well with edge lists.
Efficiency	$O(v^2)$ (matrix), $O(e \log v)$ (heap).	$O(e \log e)$ (edge sorting dominates).
Use Case	Dense graphs or pre-sorted weight matrices.	Sparse graphs or edge-heavy graphs.
Cycle Detection	Implicit (grows a tree).	Explicit (uses disjoint sets/union-find).