Kruskal vs Prim
In de informatica zijn de algoritmen van Prim en Kruskal een hebzuchtig algoritme dat een minimale opspannende boom vindt voor een verbonden gewogen ongerichte graaf. Een opspannende boom is een subgraaf van een graaf zodanig dat elk knooppunt van de graaf is verbonden door een pad, wat een boom is. Elke opspannende boom heeft een gewicht, en de minimaal mogelijke gewichten/kosten van alle opspannende bomen is de minimum opspannende boom (MST).
Meer over het algoritme van Prim
Het algoritme is in 1930 ontwikkeld door de Tsjechische wiskundige Vojtěch Jarník en later onafhankelijk door computerwetenschapper Robert C. Prim in 1957. Het werd in 1959 herontdekt door Edsger Dijkstra. Het algoritme kan in drie belangrijke stappen worden beschreven;
Gezien de verbonden grafiek met n knopen en het respectieve gewicht van elke rand, 1. Selecteer een willekeurige knoop uit de grafiek en voeg deze toe aan de boom T (die de eerste knoop zal zijn)
2. Overweeg de gewichten van elke rand die is verbonden met de knooppunten in de boom en selecteer het minimum. Voeg de rand en de knoop aan het andere uiteinde van de boom T toe en verwijder de rand uit de grafiek. (Selecteer er een als er twee of meer minima zijn)
3. Herhaal stap 2, totdat n-1 randen aan de boom zijn toegevoegd.
Bij deze methode begint de boom met een enkele willekeurige knoop en breidt zich vanaf die knoop met elke cyclus uit. Om het algoritme goed te laten werken, moet de grafiek dus een verbonden grafiek zijn. De basisvorm van het algoritme van Prim heeft een tijdcomplexiteit van O(V2).
Meer over het algoritme van Kruskal
Het door Joseph Kruskal ontwikkelde algoritme verscheen in 1956 in de procedures van de American Mathematical Society. Het algoritme van Kruskal kan ook in drie eenvoudige stappen worden uitgedrukt.
Gegeven de grafiek met n knopen en het respectieve gewicht van elke rand, 1. Selecteer de boog met het minste gewicht van de hele grafiek en voeg toe aan de boom en verwijder uit de grafiek.
2. Selecteer van de overige de minst gewogen rand, op een manier die geen cyclus vormt. Voeg de rand toe aan de boom en verwijder uit de grafiek. (Selecteer er een als er twee of meer minima zijn)
3. Herhaal het proces in stap 2.
Bij deze methode begint het algoritme met de minst gewogen rand en gaat door met het selecteren van elke rand bij elke cyclus. Daarom hoeft de grafiek in het algoritme niet te worden aangesloten. Het algoritme van Kruskal heeft een tijdcomplexiteit van O(logV)
Wat is het verschil tussen het algoritme van Kruskal en Prim?
• Het algoritme van Prim wordt geïnitialiseerd met een knoop, terwijl het algoritme van Kruskal begint met een rand.
• De algoritmen van Prim strekken zich uit van het ene knooppunt naar het andere, terwijl het algoritme van Kruskal de randen selecteert op een manier dat de positie van de rand niet gebaseerd is op de laatste stap.
• In het algoritme van prim moet de grafiek een verbonden grafiek zijn, terwijl de Kruskal's ook op niet-gekoppelde grafieken kunnen functioneren.
• Het algoritme van Prim heeft een tijdcomplexiteit van O(V2), en de tijdcomplexiteit van Kruskal is O(logV).
