AI HL · AHL 1
0 of 43 skills done
Minimum spanning trees: Kruskal's algorithm
AHL 1.8
Choose Kruskal or Prim, then press Next to watch the tree grow, or switch to "Try it yourself" and press the edge you would add. Another graph gives a new example.
The edges in order of weight ()
The graph shows the cost, in £ thousand, of laying a cable between six offices. Use Kruskal's algorithm to find a minimum spanning tree. List the edges in the order they are added and find the total weight.
Have a go first. Then open the working one line at a time.
DE 7, BE 13, AE 14, AB 17, EF 18, AD 20, CE 21, CF 28, BC 30
List every edge from the smallest weight to the largest. All the weights are different, so the order is clear.
DE 7: add; BE 13: add; AE 14: add; AB 17: reject, cycle A–E–B; EF 18: add; AD 20: reject, cycle A–E–D; CE 21: add
Take the edges in order. Add an edge unless it makes a cycle with the edges already chosen. Check by looking for a path between its two ends.
5 edges chosen: DE, BE, AE, EF, CE
A spanning tree on 6 vertices has 5 edges. Stop when you reach that number: the later edges are not needed.
7 + 13 + 14 + 18 + 21 = 73
Add the weights of the edges in the tree.
The table shows the distances, in km, between six villages. Roads are to be built so that every village can be reached from every other village, using the least total length. Use Kruskal's algorithm to find which roads to build, in the order they are added, and the total length.
Have a go first. Then open the working one line at a time.
AD 8, DF 23, AB 32, AF 33, BE 34, BF 49, AC 59, BC 61, CF 63, EF 64, DE 65, BD 68, AE 72, CE 75, CD 76
List every edge from the smallest weight to the largest. All the weights are different, so the order is clear.
AD 8: add; DF 23: add; AB 32: add; AF 33: reject, cycle A–D–F; BE 34: add; BF 49: reject, cycle B–A–D–F; AC 59: add
Take the edges in order. Add an edge unless it makes a cycle with the edges already chosen. Check by looking for a path between its two ends.
5 edges chosen: AD, DF, AB, BE, AC
A spanning tree on 6 vertices has 5 edges. Stop when you reach that number: the later edges are not needed.
8 + 23 + 32 + 34 + 59 = 156
Add the weights of the edges in the tree.
The table shows the cost, in €1000, of laying a cable directly between six schools. A dash means a cable cannot be laid between those two schools. Use Kruskal's algorithm to find a minimum spanning tree: give the edges in the order they are added and the total cost.
Have a go first. Then open the working one line at a time.
AD 10, AF 17, EF 30, CF 37, AC 42, CD 51, BF 57, DE 61, AB 74, BD 75
List every edge from the smallest weight to the largest. All the weights are different, so the order is clear.
AD 10: add; AF 17: add; EF 30: add; CF 37: add; AC 42: reject, cycle A–F–C; CD 51: reject, cycle C–F–A–D; BF 57: add
Take the edges in order. Add an edge unless it makes a cycle with the edges already chosen. Check by looking for a path between its two ends.
5 edges chosen: AD, AF, EF, CF, BF
A spanning tree on 6 vertices has 5 edges. Stop when you reach that number: the later edges are not needed.
10 + 17 + 30 + 37 + 57 = 151
Add the weights of the edges in the tree.
The graph shows the lengths, in metres, of possible paths between eight sheds on an allotment. Use Kruskal's algorithm to find a minimum spanning tree. List the edges in order and give the total length.
Have a go first. Then open the working one line at a time.
EH 2, DE 3, EF 4, FH 5, AC 8, AB 12, DF 13, BC 17, GH 18, FG 20, DG 21, BD 23
List every edge from the smallest weight to the largest. All the weights are different, so the order is clear.
EH 2: add; DE 3: add; EF 4: add; FH 5: reject, cycle F–E–H; AC 8: add; AB 12: add; DF 13: reject, cycle D–E–F; BC 17: reject, cycle B–A–C; GH 18: add; FG 20: reject, cycle F–E–H–G; DG 21: reject, cycle D–E–H–G; BD 23: add
Take the edges in order. Add an edge unless it makes a cycle with the edges already chosen. Check by looking for a path between its two ends.
7 edges chosen: EH, DE, EF, AC, AB, GH, BD
A spanning tree on 8 vertices has 7 edges. Stop when you reach that number: the later edges are not needed.
2 + 3 + 4 + 8 + 12 + 18 + 23 = 70
Add the weights of the edges in the tree.