Minimum Spanning Trees (Edexcel A-Level Further Mathematics): Flashcards

A minimum spanning tree (MST) of a connected, weighted graph

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

Sort all edges in ascending order by weight

$v-1$ edges

Disjoint sets (union-find)

$O(e \log e)$ where $e$ is the number of edges

$O(e \log e + e \log v)$

$O(v)$ for union-find structures

Connected graphs (otherwise gives spanning forest)

When edge weights are not distinct