Minimum Spanning Trees and Prim’s Algorithm (AQA A-Level Further Maths): Flashcards

Connected subgraph, all vertices, min weight, no cycles, $n-1$ edges

$n-1$ edges

Greedy algorithm

Makes locally optimal choice, picks smallest weight arc available

Only considers arcs from connected to unconnected vertices

Select any vertex

Cross out row, number column

Minimum undeleted weight in numbered columns

Choose any at random; same total weight, different valid MSTs

Prim's grows one tree; Kruskal's builds multiple fragments