Lesson 2 of 8 · 18 min

Finding minimum spanning trees

Find a minimum spanning tree and its weight by inspection, with Kruskal's method and with Prim's method, and recognise when there is more than one.

What you will be able to do

  • Find a minimum spanning tree with Kruskal's method, skipping edges that would form a cycle.
  • Find a minimum spanning tree with Prim's method from any starting vertex.
  • Find the weight of a minimum spanning tree.
  • Decide whether a minimum spanning tree is unique when some edges have equal weights.

A ranger wants to upgrade some walking tracks between seven camp sites, AA to GG, to an all-weather surface. Every camp site must be reachable on upgraded track, and the upgrade costs the same per kilometre everywhere, so the ranger wants the least total length.

That is a minimum spanning tree. You could try spanning trees at random, but this graph has 320 of them. Instead, use a method that builds the best tree one edge at a time.

Tracks between camp sites, with lengths in kilometres.

Kruskal's method

  1. List the edges from lightest to heaviest

    Write them in order of weight. Where weights are equal, the order between them does not matter.

  2. Choose the lightest edge

    It cannot make a cycle on its own.

  3. Choose the next lightest edge that does not make a cycle

    If an edge joins two vertices that are already connected by the edges you have chosen, it would close a cycle. Skip it.

  4. Stop at v − 1 edges

    Once you have v−1v - 1 edges, every vertex is joined. Add their weights to get the weight of the minimum spanning tree.

Interactive

Kruskal's method, one edge at a time

Step through Kruskal's method on the camp-site tracks. Watch the separate pieces join up, and notice which edge is skipped and why.

Worked example

Kruskal's method on the camp-site tracks

  • 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.

5 steps

Try it yourself first, then check the working one step at a time.

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.

Kruskal's method on the camp-site tracks considers ABAB (6 km) but does not choose it. Which vertices were already connected, making ABAB form a cycle?

Choose one answer

Prim's method

  1. Start at any vertex

    This vertex is the tree so far.

  2. Look at every edge leaving the tree

    These are the edges joining a vertex in the tree to a vertex not yet in it.

  3. Add the lightest of them

    Its far vertex joins the tree. Because the new vertex was not in the tree, no cycle can form.

  4. Repeat until every vertex is in the tree

    That takes v−1v - 1 edges. Add their weights.

Interactive

Prim's method from A

Step through Prim's method on the same tracks, starting at AA. The tree grows from one vertex; at each step the highlighted edges are the candidates.

Worked example

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

  • 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.

7 steps

Try it yourself first, then check the working one step at a time.

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.

Common mistake

Prim's method is not "nearest neighbour"

At each step, look at the edges from every vertex already in the tree, not just the one you added last. From AA, CC joins first (AC=4AC = 4), then DD (CD=3CD = 3), then BB (BD=5BD = 5). The next edge is DEDE (6), from DD, even though BB was the latest vertex added.

Kruskal's method

  • Works on the whole graph at once: sort every edge by weight.
  • The chosen edges can sit in separate pieces until the end.
  • You must check each edge for a cycle.
  • Easiest when the network is drawn.

Prim's method

  • Grows one tree from a starting vertex.
  • The chosen edges are always connected.
  • Cycles cannot form, so there is nothing to check.
  • Works well from a table of distances.

Tip

Inspection for small graphs

For a graph with only a few vertices you can find a minimum spanning tree by inspection: pick out the light edges, avoid cycles, and make sure every vertex is reached. That is Kruskal's method done in your head. For anything larger, name a method and show its steps.

Both methods gave the same tree of 27 km for the camp sites. But when some edges have equal weights, there can be a genuine choice. Look at the graph below: PQPQ and QRQR are both 4.

A graph with two edges of weight 4.

Worked example

A graph with two minimum spanning trees

  • Complex familiar
  • Technology free

A graph has edges PQPQ 4, PRPR 3, QRQR 4, QSQS 5, RSRS 6 and STST 2. Find the weight of a minimum spanning tree, and decide whether the minimum spanning tree is unique.

5 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Run Kruskal's method as usual.

  2. At a tie, check whether choosing one of the equal edges rules out the other. If so, each choice gives a minimum spanning tree.

Watch out for

  • Choosing both PQPQ and QRQR, which forms a cycle.

  • Thinking that two different trees must have different weights.

For the graph with vertices PP to TT above, how many different minimum spanning trees are there?

Choose one answer

Key idea

When is a minimum spanning tree unique?

If every edge weight is different, the minimum spanning tree is unique. With equal weights there may be more than one — but the minimum weight is always the same. Equal weights do not always cause a choice: on the camp-site tracks, ACAC and EGEG are both 4 and both are needed, so that tree is unique.

Exam tip

Show the order you chose the edges, name any edge you skipped and why ("ABAB would form a cycle"), list the final edges, count them (v−1v - 1), and give the total weight with units.

Summary

  • Kruskal's method: take edges from lightest to heaviest, skipping any edge that would form a cycle, until there are v−1v - 1 edges.

  • Prim's method: grow one tree from any vertex, each time adding the lightest edge from the tree to a new vertex.

  • Both methods give a minimum spanning tree; for small graphs, inspection is the same idea done mentally.

  • The weight of a minimum spanning tree is the sum of its edge weights.

  • Equal edge weights can give more than one minimum spanning tree, all with the same weight.

Finished the lesson?

Try the 2 quick checks above and the lesson completes itself, or mark it complete now.

Lesson 2 of 80% read

Save your progress with a free account