Search topics

Search
1 of 8 0-day streak

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

DIFFICULTYintrostandardexam
Question 1 of 8

Calculator allowed

The network shows roads between coastal towns. Each edge label gives the road distance in kilometres

Weighted network. Vertices in listed order: [Apollo Bay | Warrnambool | Torquay | Port Fairy | Portland]. Full edge list: Portland–Torquay (26 km); Apollo Bay–Torquay (42 km); Apollo Bay–Portland (50 km); Torquay–Warrnambool (10 km); Warrnambool–Portland (28 km); Port Fairy–Apollo Bay (54 km); Port Fairy–Torquay (38 km); Port Fairy–Portland (46 km).26 km42 km50 km10 km28 km54 km38 km46 kmApollo BayWarrnamboolTorquayPort FairyPortland
(a)4 marks

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

(b)1 mark

Calculate the total weight of the minimum spanning tree