Minimum spanning trees

Minimum spanning trees

Spec 2.1 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A spanning tree joins every vertex with no cycles, so a network with nn vertices has a spanning tree of exactly n−1n-1 edges.
  • A minimum spanning tree is the spanning tree with the least total weight.
  • Kruskal's algorithm sorts the edges and accepts each one unless it forms a cycle.
  • Prim's algorithm grows one tree from a start vertex, always adding the shortest edge to a new vertex.
  • On a matrix, Prim's algorithm numbers columns and deletes rows as vertices join the tree.

The minimum spanning tree

A minimum spanning tree connects every vertex using the least total weight, with no cycles.

A spanning tree connects all the vertices of a network with no cycles. The minimum spanning tree is the one with the smallest total weight, such as the cheapest cables joining all the sites.

If all the weights are different it is unique. If some weights are equal there may be more than one.

Two algorithms find it: Kruskal's and Prim's.

  • Verticesnn
  • Edges in a spanning treen−1n-1

A network has 9 vertices. How many edges does a spanning tree of it have?

Kruskal's algorithm

Sort the edges by weight, then accept each in turn unless it forms a cycle. Stop when n−1n-1 edges are accepted.

Kruskal's algorithm works on the sorted list of edges.

  1. Sort the edges in increasing order of weight.
  2. Take the next edge. Accept it unless it forms a cycle with the edges already accepted.
  3. Stop when n−1n-1 edges are accepted.

Test whether the two ends are already connected, not whether the vertices are already in the tree.

DE 3AC 4CD 5BC 6AB 7CE 8BD 9EF 10DF 12ABCDEF
Accepted edges are solid, rejected edges dashed.

Worked example

Six vertices, edges DE=3DE=3, AC=4AC=4, CD=5CD=5, BC=6BC=6, AB=7AB=7, CE=8CE=8, BD=9BD=9, EF=10EF=10, DF=12DF=12. Find the minimum spanning tree.

Edges AB=2AB=2, BC=3BC=3, AC=4AC=4 are considered in order. Which is rejected?

Prim's algorithm

Start at any vertex and keep adding the shortest edge that joins the tree to a vertex outside it. Cycles cannot form.

Prim's algorithm grows a single tree from any starting vertex.

  1. Choose any vertex to start.
  2. Look at all edges from a vertex in the tree to a vertex not in it. Add the shortest.
  3. Repeat until every vertex is in the tree.

Because the tree stays connected as it grows, cycles can never form.

  1. 1

    Start

    choose any vertex

  2. 2

    Look

    edges from the tree to new vertices

  3. 3

    Add

    the shortest of these

  4. 4

    Repeat

    until all vertices are in the tree

Prim's algorithm

Worked example

Edges AB=6AB=6, AC=9AC=9, BC=4BC=4, BD=8BD=8, CD=7CD=7, CE=5CE=5, DE=3DE=3. Use Prim's algorithm from AA.

After adding AB(6)AB(6) in the example, which edge does Prim's algorithm add next?

Prim's on a matrix

Number the start column, delete its row, then repeatedly circle the smallest entry in the numbered columns among undeleted rows.

A distance matrix lists the weight between every pair of vertices, with a dash where there is no edge.

  1. Choose a start vertex. Number its column 1 and delete its row.
  2. In the numbered columns, circle the smallest entry in a row not yet deleted.
  3. That row is the new vertex. Number its column next and delete the row.
  4. Repeat until all rows are deleted.

The matrix of an undirected network is symmetric, so each edge appears twice.

  1. 1

    Start

    number the start column 1 and delete its row

  2. 2

    Circle

    the smallest entry in numbered columns, in rows not deleted

  3. 3

    Number

    the circled row's column next, then delete the row

  4. 4

    Repeat

    until every row is deleted

Prim's algorithm on a matrix

The matrix of an undirected network has 14 numerical entries in total. How many edges does the network have?

Try an exam question

A network has edges AB=5AB=5, AC=8AC=8, BC=6BC=6, BD=9BD=9, CD=7CD=7, CE=11CE=11, DE=10DE=10. Use Kruskal's algorithm to find a minimum spanning tree. State the edges in the order considered and the total weight.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

How many edges does a minimum spanning tree of this network contain?

1 mark, marked against the mark scheme

Revision notes