Kruskal tegen Prim
In de informatica zijn de algoritmen van Prim en Kruskal een hebzuchtig algoritme dat een minimale spanning tree vindt voor een verbonden gewogen ongerichte graaf. Een spanning tree is een subgraaf van een graaf zodat elk knooppunt van de graaf is verbonden door een pad, dat een boom is. Elke spanning tree heeft een gewicht, en de minimaal mogelijke gewichten / kosten van alle spanning trees is de minimum spanning tree (MST).
Meer over het algoritme van Prim
Het algoritme is ontwikkeld door de Tsjechische wiskundige Vojtěch Jarník in 1930 en later onafhankelijk door computerwetenschapper Robert C. Prim in 1957. Het werd herontdekt door Edsger Dijkstra in 1959. Het algoritme kan in drie belangrijke stappen worden uitgedrukt;
Gegeven de verbonden grafiek met n knooppunten en het respectieve gewicht van elke rand, 1. Selecteer een willekeurig knooppunt uit de grafiek en voeg het toe aan de boom T (dit wordt het eerste knooppunt)
2. Overweeg de gewichten van elke rand die is verbonden met de knooppunten in de boom en selecteer het minimum. Voeg de rand en het knooppunt aan het andere uiteinde van de boom T toe en verwijder de rand uit de grafiek. (Selecteer een van de twee of meer minima)
3. Herhaal stap 2 totdat er n-1 randen aan de boom zijn toegevoegd.
Bij deze methode begint de boom met een enkel willekeurig knooppunt en breidt zich vanaf dat knooppunt uit met elke cyclus. Om het algoritme correct te laten werken, moet de grafiek een verbonden grafiek zijn. De basisvorm van het algoritme van de Prim heeft een tijdcomplexiteit van O (V 2).
Meer over het algoritme van Kruskal
Het door Joseph Kruskal ontwikkelde algoritme verscheen in 1956 in de procedure van de American Mathematical Society. Het algoritme van Kruskal kan ook in drie eenvoudige stappen worden uitgedrukt.
Gegeven de grafiek met n knooppunten 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 deze 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 deze uit de grafiek. (Selecteer een van de opties als er twee of meer minima bestaan)
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 in het algoritme de grafiek niet te worden verbonden. 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 initialiseert 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 zo selecteert dat de positie van de rand niet gebaseerd is op de laatste stap.
• In het algoritme van prim moet de graaf een verbonden graaf zijn, terwijl de Kruskal's ook kunnen werken op niet-verbonden grafieken.
• Het algoritme van Prim heeft een tijdcomplexiteit van O (V 2), en de tijdcomplexiteit van Kruskal is O (logV).
