Prim's Algorithm (Edexcel A-Level Further Mathematics): Flashcards

Minimum spanning tree (MST)

Adds the smallest connecting edge at each step

When graph is represented as a matrix

Select any vertex to begin the MST

When all vertices are included in the MST

No edge exists between vertices $i$ and $j$

$O(v^2)$

$O(v^2)$

$v-1$ edges

Total weight of edges