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 power lines between service sites. Each edge label gives the installation cost in dollars

Weighted network. Vertices in listed order: [Hospital | Workshop | Pump | Substation | Depot]. Full edge list: Workshop–Pump ($812); Hospital–Pump ($240); Depot–Hospital ($590); Substation–Hospital ($232); Depot–Workshop ($828); Pump–Substation ($198); Depot–Pump ($366); Workshop–Hospital ($254).$812$240$590$232$828$198$366$254HospitalWorkshopPumpSubstationDepot
(a)4 marks

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

(b)1 mark

Find the minimum total installation cost needed to connect every vertex