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

Consider this network of walking tracks between park locations. Each edge label gives the walking distance in kilometres

Weighted network. Vertices in listed order: [Picnic Area | Lake | Lookout | Shelter | Ranger Station]. Full edge list: Shelter–Picnic Area (4 km); Shelter–Lookout (24 km); Ranger Station–Lake (32 km); Ranger Station–Lookout (20 km); Lake–Lookout (16 km); Shelter–Lake (2 km); Picnic Area–Lake (6 km); Shelter–Ranger Station (30 km).4 km24 km32 km20 km16 km2 km6 km30 kmPicnic AreaLakeLookoutShelterRanger Station
(a)4 marks

Apply Prim's algorithm, starting at Ranger Station. Enter the edge weights in their addition order

(b)1 mark

Find the minimum total walking distance needed to connect every vertex