Search topics

Search
1 of 8 0-day streak

Minimum spanning trees by Prim's and Kruskal's algorithms

DIFFICULTYintrostandardchallengeexam
Question 1 of 8

Calculator allowed

The network shows paths between campus buildings. Each edge label gives the walking time in minutes

Weighted network. Vertices in listed order: [Canteen | Library | Hall | Science | Arts]. Full edge list: Canteen–Library (6 minutes); Arts–Library (16 minutes); Hall–Canteen (14 minutes); Canteen–Arts (18 minutes); Canteen–Science (22 minutes); Science–Arts (30 minutes); Library–Hall (12 minutes); Hall–Science (24 minutes).6 minutes16 minutes14 minutes18 minutes22 minutes30 minutes12 minutes24 minutesCanteenLibraryHallScienceArts
(a)4 marks

Starting from Arts, use Prim's algorithm. Record each selected weight in order

(b)1 mark

Calculate the total weight of the minimum spanning tree