Verschil tussen Kruskal en Prim
Share
Kruskal tegen Prim
In de informatica zijn de algoritmen van Prim en Kruskal een hebzuchtig algoritme dat een minimale spanningboom voor een gekoppelde gewogen ongerichte grafiek vindt. Een spanning tree is een subgraph van een grafiek, zodat elk knooppunt van de grafiek is verbonden door een pad, dat is een boom. Elke spanningboom heeft een gewicht en de minimaal mogelijke gewichten / kosten van alle omspannende bomen is de minimale spanningboom (MST).
Meer over Prim's algoritme
Het algoritme werd 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 beschreven;
Gegeven de verbonden grafiek met n knooppunten en respectieve gewicht van elke rand,
1. Selecteer een willekeurig knooppunt uit de grafiek en voeg het toe aan de boom T (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 toe aan het andere uiteinde van de boom T en verwijder de rand van de grafiek. (Selecteer een optie als er twee of meer minima bestaan)
3. Herhaal stap 2 totdat n-1 randen aan de boom zijn toegevoegd.
In deze methode begint de boom met een enkel willekeurig knooppunt en breidt vanaf dat knooppunt uit met elke cyclus. Daarom moet het algoritme voor de juiste werking van het algoritme een gekoppelde 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 de procedure van de American Mathematical Society in 1956. Kruskal's algoritme kan ook in drie eenvoudige stappen worden uitgedrukt.
Gegeven de grafiek met n knooppunten en respectieve gewicht van elke rand,
1. Selecteer de boog met het laagste gewicht van de hele grafiek en voeg deze toe aan de boom en wis deze uit de grafiek.
2. Selecteer van de overgeblevenen 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 optie 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 blijft het elke rand van elke cyclus selecteren. Daarom hoeft de grafiek in het algoritme niet verbonden te zijn. Kruskal's algoritme 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 knooppunt, terwijl het algoritme van Kruskal begint met een edge.
• De algoritmen van Prim gaan van het ene knooppunt naar het andere terwijl het algoritme van Kruskal de randen zodanig selecteert dat de positie van de rand niet op de laatste stap is gebaseerd.
• In het algoritme van prim moet de grafiek een verbonden grafiek zijn, terwijl de Kruskal ook op niet-verbonden grafieken kan werken.
• Het algoritme van Prim heeft een tijdcomplexiteit van O (V2), en de tijdcomplexiteit van Kruskal is O (logV).
