Kruskal vs Prim
In rekenaarwetenskap is Prim en Kruskal se algoritmes 'n gulsige algoritme wat 'n minimum spanningsboom vir 'n gekoppelde geweegde ongerigte grafiek vind. 'n Spanningboom is 'n subgrafiek van 'n grafiek sodat elke nodus van die grafiek deur 'n pad verbind word, wat 'n boom is. Elke spanboom het 'n gewig, en die minimum moontlike gewigte/koste van al die spanningbome is die minimum spanboom (MST).
Meer oor Prim se algoritme
Die algoritme is in 1930 deur die Tsjeggiese wiskundige Vojtěch Jarník ontwikkel en later onafhanklik deur die rekenaarwetenskaplike Robert C. Prim in 1957. Dit is in 1959 deur Edsger Dijkstra herontdek. Die algoritme kan in drie sleutelstappe gestel word;
Gegewe die gekoppelde grafiek met n nodes en onderskeie gewig van elke rand, 1. Kies 'n arbitrêre nodus uit die grafiek en voeg dit by die boom T (wat die eerste nodus sal wees)
2. Oorweeg die gewigte van elke rand wat aan die nodusse in die boom gekoppel is en kies die minimum. Voeg die rand en die nodus aan die ander kant van die boom T by en verwyder die rand van die grafiek. (Kies enige as daar twee of meer minimums bestaan)
3. Herhaal stap 2 totdat n-1 rande by die boom gevoeg is.
In hierdie metode begin die boom met 'n enkele arbitrêre nodus en brei van daardie nodus af en verder met elke siklus. Dus, vir die algoritme om behoorlik te werk, moet die grafiek 'n gekoppelde grafiek wees. Die basiese vorm van die Prim se algoritme het 'n tydkompleksiteit van O(V2).
Meer oor Kruskal se Algoritme
Die algoritme wat deur Joseph Kruskal ontwikkel is, het in die verrigtinge van die American Mathematical Society in 1956 verskyn. Kruskal se algoritme kan ook in drie eenvoudige stappe uitgedruk word.
Gegewe die grafiek met n nodusse en onderskeie gewig van elke rand, 1. Kies die boog met die minste gewig van die hele grafiek en voeg by die boom en vee uit die grafiek.
2. Van die oorblywende kies die minste geweegde rand, op 'n manier wat nie 'n siklus vorm nie. Voeg die rand by die boom en vee uit die grafiek. (Kies enige as daar twee of meer minimums bestaan)
3. Herhaal die proses in stap 2.
In hierdie metode begin algoritme met die minste geweegde rand en gaan voort om elke rand by elke siklus te kies. In die algoritme hoef die grafiek dus nie verbind te wees nie. Kruskal se algoritme het 'n tydskompleksiteit van O(logV)
Wat is die verskil tussen Kruskal se en Prim se Algoritme?
• Prim se algoritme inisieer met 'n nodus, terwyl Kruskal se algoritme met 'n rand begin.
• Prim se algoritmes strek van een nodus na 'n ander terwyl Kruskal se algoritme die rande op 'n manier kies dat die posisie van die rand nie op die laaste stap gebaseer is nie.
• In prim se algoritme moet grafiek 'n gekoppelde grafiek wees terwyl die Kruskal's ook op ontkoppelde grafieke kan funksioneer.
• Prim se algoritme het 'n tydkompleksiteit van O(V2), en Kruskal se tydkompleksiteit is O(logV).
