Lesson 2: Finding minimum spanning trees

Prim's method from A on the camp-site tracks

SkillFinding minimum spanning trees

Worked example

  • Simple familiar
  • Technology free

Use Prim's method, starting at AA, to find a minimum spanning tree for the camp-site tracks. List the edges in the order they are added.

1 of 7 steps
  1. Step 1: Start at A

    Edges leaving {A}\{A\}: ABAB 6, ACAC 4, ADAD 7. Add the lightest, ACAC (4).

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. Start with one vertex as the tree.

  2. List the edges joining the tree to a vertex not in it; add the lightest.

  3. Repeat until every vertex is in the tree.

Watch out for

  • Only looking at edges from the newest vertex. After BB joins, the next edge (DEDE) comes from DD.

Save your progress with a free account