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

A subset of edges connecting all vertices with minimum total weight and no cycles

Grows connected MST from single vertex

Adds smallest edges, ensuring no cycles

Works well with adjacency matrices

Works well with edge lists

$O(v^2)$

$O(e log e)$

Dense graphs or pre-sorted weight matrices

Sparse graphs or edge-heavy graphs

Explicit (uses disjoint sets/union-find)