Kruskal vs Prim
A számítástechnikában a Prim- és a Kruskal-algoritmusok egy mohó algoritmusok, amelyek megtalálják a minimális feszítőfát egy összekapcsolt súlyozott irányítatlan gráfhoz. A feszítőfa a gráf olyan részgráfja, amelyben a gráf minden csomópontját egy útvonal köti össze, amely egy fa. Minden feszítőfának van súlya, és az összes feszítőfa minimális lehetséges súlya/költsége a minimális feszítőfa (MST).
További információ a Prim algoritmusáról
Az algoritmust Vojtěch Jarník cseh matematikus fejlesztette ki 1930-ban, később önállóan, Robert C. Prim informatikus, 1957-ben. Edsger Dijkstra fedezte fel újra 1959-ben. Az algoritmust három kulcslépésben lehet megfogalmazni;
Az n csomóponttal és az egyes élek megfelelő súlyával összekapcsolt gráfot figyelembe véve
1. Válasszon ki egy tetszőleges csomópontot a gráfból, és adja hozzá a T fához (ami lesz az első csomópont)
2. Vegye figyelembe a fa csomópontjaihoz kapcsolódó egyes élek súlyát, és válassza ki a minimumot. Adja hozzá az élt és a csomópontot a T fa másik végén, és távolítsa el az élt a gráfból. (Válassza ki bármelyiket, ha kettő vagy több minimum létezik)
3. Ismételje meg a 2. lépést, amíg n-1 élt hozzáad a fához.
Ennél a módszernél a fa egyetlen tetszőleges csomóponttal kezdődik, és ettől a csomóponttól kezdve minden ciklussal bővül. Ezért ahhoz, hogy az algoritmus megfelelően működjön, a gráfnak összefüggő gráfnak kell lennie. A Prim-algoritmus alapformájának időbonyolítása O(V2).
További információ a Kruskal-algoritmusról
A Joseph Kruskal által kifejlesztett algoritmus 1956-ban jelent meg az Amerikai Matematikai Társaság közleményében. Kruskal algoritmusa három egyszerű lépésben is kifejezhető.
Az n csomópontot tartalmazó gráf és az egyes élek megfelelő súlya alapján
1. Válassza ki a legkisebb súlyú ívet a teljes grafikonon, és adja hozzá a fához, és törölje a grafikonból.
2. A többi közül válassza ki a legkevésbé súlyozott élt úgy, hogy ne képezzen ciklust. Adja hozzá az élt a fához, és törölje a grafikonból. (Válassza ki bármelyiket, ha kettő vagy több minimum létezik)
3. Ismételje meg a folyamatot a 2. lépésben.
Ennél a módszernél az algoritmus a legkisebb súlyozott éllel kezdődik, és minden egyes ciklusban folytatja az egyes élek kiválasztását. Ezért az algoritmusban a gráfot nem kell összekapcsolni. Kruskal algoritmusának időbonyolultsága O(logV)
Mi a különbség a Kruskal- és a Prim-algoritmus között?
• A Prim algoritmusa egy csomóponttal inicializálódik, míg a Kruskal algoritmusa egy éllel.
• A Prim algoritmusai egyik csomóponttól a másikig terjednek, míg Kruskal algoritmusa úgy választja ki az éleket, hogy az él pozíciója ne az utolsó lépésen alapuljon.
• A prim algoritmusában a gráfnak összefüggő gráfnak kell lennie, míg a Kruskal-féle gráfok szétválasztott gráfokon is működhetnek.
• A Prim algoritmusának időbonyolultsága O(V2), Kruskal időbonyolultsága pedig O(logV).
