Solve minimum-connector problems using trees and greedy methods.
Key skillsSolve minimum-connector problems using trees and greedy methods.
Build the idea
A spanning tree connects every vertex without a cycle. A minimum spanning tree minimises the total weight of those selected edges. Prim’s procedure starts with one vertex and repeatedly adds a cheapest edge crossing from the current tree to an outside vertex. This preserves connectedness and avoids cycles; equal choices may produce different optimal trees.
Try the sample task
Use Prim’s algorithm from A on AB=4, AC=2, BC=1, BD=5, CD=7, CE=3 and ED=1. Record the chosen edge and the growing vertex set at every step.
The full worksheet includes the worked solution and remaining task set.
What this activity covers
This focused activity develops the stated idea through one context. It is practice, not evidence that every application or subclause of a broad study-design bullet has been mastered.