Ik vroeg me af wanneer je Prim’s algoritmemoet gebruiken en wanneer Kruskal’som de minimale opspannende boom te vinden? Ze hebben allebei eenvoudige logica, dezelfde slechtste gevallen, en het enige verschil is de implementatie die een beetje verschillende datastructuren kan inhouden. Dus wat is de beslissende factor?
Antwoord 1, autoriteit 100%
Gebruik het algoritme van Prim als je een grafiek hebt met veel randen.
Voor een grafiek met Vhoekpunten Eranden, loopt het algoritme van Kruskal in O(E log V)tijd en kan het algoritme van Prim in O(E + V log V)afgeschreven tijd, als je een Fibonacci Heap.
Het algoritme van Prim is aanzienlijk sneller in de limiet als je een erg dichte grafiek hebt met veel meer randen dan hoekpunten. Kruskal presteert beter in typische situaties (dunne grafieken) omdat het eenvoudigere gegevensstructuren gebruikt.
Antwoord 2, autoriteit 52%
Ik vond een heel mooi draadje op het net dat het verschil op een heel duidelijke manier uitlegt: http: //www.thestudentroom.co.uk/showthread.php?t=232168.
Het algoritme van Kruskal laat een oplossing groeien vanaf de goedkoopste rand door de volgende goedkoopste rand toe te voegen, op voorwaarde dat er geen cyclus ontstaat.
Prim’s algoritme laat een oplossing groeien vanuit een willekeurig hoekpunt door het volgende goedkoopste hoekpunt toe te voegen, het hoekpunt dat zich momenteel niet in de oplossing bevindt, maar ermee verbonden is door de goedkoopste rand.
Hier bijgevoegd is een interessant blad over dat onderwerp.
Als je zowel Kruskal als Prim implementeert, in hun optimale vorm: met respectievelijk een unie-vondst en een finbonacci-heap, dan zul je merken hoe Kruskal gemakkelijk te implementeren is in vergelijking met Prim.
Prim is moeilijker met een fibonacci-heap, vooral omdat je een boekhoudtabel moet bijhouden om de bidirectionele link tussen grafiekknooppunten en heap-knooppunten vast te leggen. Met een Union Find is het tegenovergestelde het geval, de structuur is eenvoudig en kan zelfs direct de mst produceren, bijna zonder extra kosten.
Antwoord 3, autoriteit 16%
Ik weet dat je hier niet om hebt gevraagd, maar als je meer verwerkingseenheden hebt, moet je altijd rekening houden met Borůvka’s algoritme, omdat het gemakkelijk kan worden geparalleliseerd – vandaar dat het een prestatievoordeel heeft ten opzichte van het Kruskal- en Jarník-Prim-algoritme.
Antwoord 4, autoriteit 12%
Kruskaltijdcomplexiteit in het slechtste geval is O(E log E), dit omdat we de randen moeten sorteren.
Primtijd complexiteit in het slechtste geval is O(E log V)met prioriteitswachtrijof zelfs beter, O(E+V log V) )met Fibonacci Heap.
We zouden Kruskal moeten gebruiken als de grafiek schaars is, d.w.z. een klein aantal randen, zoals E=O(V), als de randen al gesorteerd zijn of als we ze in lineaire tijd kunnen sorteren.
We moeten Prim gebruiken als de grafiek dicht is, d.w.z. het aantal randen is hoog, zoals E=O(V²).
Antwoord 5, autoriteit 11%
Kruskal kan betere prestaties leveren als de randen in lineaire tijd kunnen worden gesorteerd of al zijn gesorteerd.
prim is beter als het aantal randen naar hoekpunten hoog is.
Antwoord 6, Autoriteit 9%
Als we stoppen met het algoritme in het algoritme van Midden-Prim altijd een aangesloten boom genereert, kan KRUSKAL aan de andere kant losgekoppelde boom of bossen
Antwoord 7, Autoriteit 2%
Een belangrijke toepassing van het algoritme van Kruskal is in enkele link clustering .
Overweeg N-hoekpunten en u hebt een complete grafiek. Om AK-clusters van die N-punten te verkrijgen .Run Kruskal’s algoritme over de eerste N- (K-1) randen van de gesorteerde set van randen. U krijgt K-Cluster van de grafiek met maximale afstand.
Antwoord 8
De beste tijd voor Kruskal’s is O (e Logv). Voor Prim’s met behulp van FIB-hopen kunnen we O (e + V LGV) krijgen. Daarom is Prim’s op een dichte grafiek veel beter.
Antwoord 9
Prim’s is beter voor meer dichte grafieken, en hierin hoeven we ook niet veel aandacht te schenken aan cycli door een rand toe te voegen, omdat we voornamelijk omgaan met knooppunten. Prim’s is sneller dan Kruskal’s in het geval van complexe grafieken.
Antwoord 10
In Kruskal-algoritme hebben we een aantal randen en het aantal hoekpunten op een gegeven grafiek, maar op elke rand hebben we een waarde of gewicht namens waarvan we een nieuwe grafiek kunnen voorbereiden die niet cyclisch moet zijn of niet in de buurt van de zijkant is
Bijvoorbeeld
graph like this
_____________
| | |
| | |
|__________| |
Naam geven aan elke vertex A, B, C, D, E, f.