Lesson 2: Finding minimum spanning trees
Prim's method from A on the camp-site tracks
SkillFinding minimum spanning trees
Worked example
Use Prim's method, starting at , to find a minimum spanning tree for the camp-site tracks. List the edges in the order they are added.
Step 1: Start at A
Edges leaving : 6, 4, 7. Add the lightest, (4).
Step 2: Tree {A, C}
Edges to new vertices: 6, 7, 3, 10. Add (3).
Step 3: Tree {A, C, D}
Candidates: 6, 5, 6, 8, 9, 10. Add (5).
is no longer a candidate: both its ends are in the tree, so it would make a cycle.
Step 4: Tree {A, B, C, D}
Candidates: 9, 6, 8, 9, 10. Add (6).
Step 5: Tree {A, B, C, D, E}
Candidates: 4, 8, 9, 10. Add (4).
Step 6: Tree {A, B, C, D, E, G}
Candidates: 5, 8, 10. Add (5). Every vertex is now in the tree.
Step 7: Add the weights
Answer
Edges in order: , , , , , . The minimum spanning tree has weight 27 km — the same tree Kruskal's method found.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
Start with one vertex as the tree.
List the edges joining the tree to a vertex not in it; add the lightest.
Repeat until every vertex is in the tree.
Watch out for
Only looking at edges from the newest vertex. After joins, the next edge () comes from .