Lesson 2: Finding minimum spanning trees

Kruskal's method on the camp-site tracks

SkillFinding minimum spanning trees

Worked example

  • Simple familiar
  • Technology free

Use Kruskal's method to find a minimum spanning tree for the camp-site tracks (lengths in km), and state its weight.

Edges: ABAB 6, ACAC 4, ADAD 7, BDBD 5, BEBE 9, CDCD 3, CFCF 10, DEDE 6, DFDF 8, EGEG 4, FGFG 5, DGDG 9.

1 of 5 steps
  1. Step 1: Order the edges by weight

    CDCD 3, ACAC 4, EGEG 4, BDBD 5, FGFG 5, ABAB 6, DEDE 6, ADAD 7, DFDF 8, BEBE 9, DGDG 9, CFCF 10.

Try a similar one

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

Method

  1. List the edges from lightest to heaviest.

  2. Choose each edge in turn unless it makes a cycle.

  3. Stop at v−1v - 1 edges and add the weights.

Watch out for

  • Choosing ABAB as well: a seventh edge always creates a cycle.

  • Stopping at FGFG: {E,F,G}\{E, F, G\} is not yet joined to the rest.

Save your progress with a free account