Het bepalen van een opspannende boom is een veelvoorkomend grafenprobleem. Een netwerk van ethernetkabels zal bijvoorbeeld vaak aangelegd worden met redundante kabels. Het spanning tree protocol (STP) zal dynamisch een opspannende boom berekenen en daarmee lussen (cykels) vermijden, verbindingen vervangen wanneer kabels (bogen) het begeven en toch steeds de routes (paden) tussen elke paar nodes voorzien.

Bij het opstellen van een opspannende boom tussen nodes is het voordelig om de vertraging (latency) op het netwerk te minimaliseren. Men zou, als we aan elke verbinding de latency op die verbinding toekennen, dit probleem kunnen herformuleren als het bepalen van een minimale-kost opspannende boom. In de praktijk wordt niet de latency tussen elke twee nodes geminimaliseerd, maar de latency tussen elke node en een root node, waar dan de uplink (de weg naar de rest van het internet) van het lokaal netwerk is.

In deze oefening implementeren we het algoritme van Prim voor het bepalen van een minimale-kost opspannende boom in een gewogen samenhangende graaf.

Schrijf een functie prim(graaf:dict) die een adjacentielijst van een graaf binnenkrijgt, en een adjacentielijst van een minimale-kost opspannende boom voor die graaf teruggeeft.

Elke top in de inkomende adjacentielijst verwijst naar een lijst van tuples, waarbij het eerste element van de tuple de afstand naar de naburige top is, en het tweede element de naam van de naburige top.

In de resulterende graaf mogen de gewichten niet meer opgenomen worden.

Voorbeeld:

>>> prim({'u':[(1,'v'),(2,'w'),(3,'x'),(5,'y')], 'v':[(1,'u'),(2,'w'),(4,'x'),(5,'y')], 'w':[(2,'u'),(2,'v'),(6,'x')], 'x':[(3,'u'), (6,'w'),(4,'v'),(2,'y')], 'y':[(5,'u'),(2,'x'),(5,'v')]})
{'u': ['v', 'w', 'x'], 'v': ['u'], 'w': ['u'], 'x': ['y', 'u'], 'y': ['x']}