Het algoritme van Prim
Stel je voor dat je kabel legt vanaf een elektriciteitscentrale: je sluit eerst de dichtstbijzijnde stad aan, dan de stad die het dichtst bij iets ligt dat al aangesloten is, enzovoort. Dat is het algoritme van Prim, en het eindigt altijd met het goedkoopst mogelijke netwerk.
Het idee
Een minimale opspannende boom verbindt elke knoop van een gewogen graaf met de kleinst mogelijke totale kantlengte. Het algoritme van Prim bouwt hem door één boom vanaf een start naar buiten te laten groeien. De boom valt nooit uiteen in stukken: bij elke stap sluit er precies één nieuwe knoop aan, via de kortste kant die uit de boom leidt.
Stap voor stap
Zet de start in de boom. Houd voor elke knoop buiten de boom zijn beste kant bij: zijn kortste kant naar een knoop in de boom. Herhaal dan: kies de knoop buiten de boom met de kortste beste kant, voeg hem met die kant toe aan de boom en bekijk zijn kanten. Een buur buiten de boom die nu via een kortere kant te bereiken is, krijgt die kant als nieuwe beste kant. Stop als elke knoop in de boom zit.
Een voorbeeld
Neem de kanten A–B met lengte 1, B–C 2, A–C 3, C–D 4 en B–D 5, en begin bij A. De kanten van A geven B de beste kant 1 en C de beste kant 3. B ligt het dichtst bij, dus B sluit aan via A–B; de kanten van B verbeteren C naar 2 en geven D 5. C sluit aan via B–C, en de kant C–D verbetert D naar 4. Ten slotte sluit D aan via C–D. De boom A–B, B–C, C–D heeft totale lengte 1 + 2 + 4 = 7.
Waarom het klopt
Bij elke stap zijn de knopen verdeeld in twee groepen: die in de boom en die erbuiten. De snede-eigenschap zegt dat de kortste kant tussen twee zulke groepen altijd bij een minimale opspannende boom hoort. Prim voegt steeds precies die kant toe, dus de boom tot nu toe kan altijd worden aangevuld tot een minimale opspannende boom, en als elke knoop is aangesloten, is hij er een.
Geschiedenis en snelheid
De Tsjechische wiskundige Vojtěch Jarník publiceerde het algoritme in 1930. Robert Prim ontdekte het opnieuw bij Bell Labs in 1957, en Edsger Dijkstra nog eens in 1959. Met de wachtende knopen in een binaire heap groeit het werk met E log V, voor V knopen en E kanten; met een gewone array is het ongeveer V², wat beter is als bijna elk paar knopen verbonden is. Met een Fibonacci-heap is het E + V log V.
Probeer het zelf
Open de app, klik op een knoop om daar te beginnen en druk op Stap. Knopen in de boom zijn groen, wachtende knopen blauw, en de beste kant van elke wachtende knoop is gestreept getekend. Onder de graaf staan de wachtende knopen met de lengte van hun beste kant, kortste eerst: de eerste sluit als volgende aan. Begin bij verschillende knopen en zie hoe de volgorde verandert terwijl het totaal gelijk blijft.
Veelgestelde vragen
Wat is het verschil tussen het algoritme van Prim en dat van Dijkstra?
Beide laten een gebied groeien vanaf een start met een prioriteitswachtrij. Prim rangschikt een wachtende knoop op de lengte van zijn ene beste kant naar de boom; Dijkstra op zijn hele afstand tot de start. Prim geeft een minimale opspannende boom, Dijkstra een boom van kortste paden.
Werkt het algoritme van Prim met negatieve kantlengtes?
Ja. Anders dan het algoritme van Dijkstra vergelijkt Prim alleen kanten met elkaar, dus negatieve lengtes zijn geen probleem: het vindt nog steeds een opspannende boom met het kleinste totaal.
Wat als de graaf niet samenhangend is?
Dan stopt het algoritme van Prim zodra het elke bereikbare knoop heeft bereikt: het geeft alleen een minimale opspannende boom van het stuk met de start. Laat je het opnieuw lopen vanaf een knoop die nog niet bereikt is, dan krijg je een minimaal opspannend bos.
Is het algoritme van Prim of dat van Kruskal beter?
Geen van beide wint altijd. Prim past bij dichte grafen en grafen die als burenlijsten zijn opgeslagen; Kruskal bij ijle grafen die als lijst van kanten gegeven zijn. Beide vinden een boom met dezelfde totale lengte.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Probeer het algoritme van Prim