Kruskal vs Prim
A számítástechnikában Prim és Kruskal algoritmusai kapzsi algoritmusok, amelyek minimálisan átfedő fát találnak egy összekapcsolt súlyozott irányítatlan gráfhoz. Az átívelő fa egy olyan gráf részgráfja, amelynél a gráf minden csomópontját egy útvonal köti össze, amely egy fa. Mindegyik átívelő fának van súlya, és az összes átnyúló fa minimális lehetséges súlya / költsége a legkisebb átfogó fa (MST).
További információ Prim algoritmusáról
Az algoritmust Vojtěch Jarník cseh matematikus fejlesztette ki 1930-ban, később pedig függetlenül Robert C. Prim informatikus 1957-ben. Edsger Dijkstra 1959-ben fedezte fel újra. Az algoritmust három fő lépésben lehet megadni;
Tekintettel az összekapcsolt gráfra, ahol n csomópont és az egyes élek megfelelő súlya van, 1. Válasszon ki egy tetszőleges csomópontot a grafikonból, és adja hozzá a T fához (ez 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 élet és a T fa másik végén lévő csomópontot, és távolítsa el az élet a grafikonról. (Válasszon egyet, ha két vagy több minimum létezik)
3. Ismételje meg a 2. lépést, amíg n-1 él hozzá nem kerül a fához.
Ebben a módszerben a fa egyetlen tetszőleges csomópontból indul, és ettől a csomóponttól kezdve minden ciklusban kibővül. Ezért az algoritmus megfelelő működéséhez a gráfnak összekapcsolt gráfnak kell lennie. A Prim algoritmus alapformájának időbeli összetettsége O (V 2).
További információ Kruskal algoritmusáról
A Joseph Kruskal által kifejlesztett algoritmus 1956-ban jelent meg az American Mathematical Society munkájában. Kruskal algoritmusa három egyszerű lépésben is kifejezhető.
Adva a grafikont n csomóval és az egyes élek megfelelő tömegével, 1. Válassza ki az egész gráf legkisebb súlyú ívét, és adja hozzá a fához, és törölje a grafikonról.
2. A fennmaradó részek közül válassza ki a legkevésbé súlyozott éleket oly módon, hogy ne képezzen ciklust. Adja hozzá az éle a fához, és törölje a grafikonról. (Válasszon egyet, ha két vagy több minimum létezik)
3. Ismételje meg a folyamatot a 2. lépésben.
Ebben a módszerben az algoritmus a legkevésbé súlyozott éllel indul, és folytatja az egyes élek kiválasztását az egyes ciklusokban. Ezért az algoritmusban a grafikont nem kell összekapcsolni. Kruskal algoritmusának időbeli összetettsége O (logV)
Mi a különbség Kruskal és Prim algoritmusa között?
• Prim algoritmusa egy csomópontnál inicializálódik, míg Kruskal algoritmusa éllel indul.
• Prim algoritmusai egyik csomópontról a másikra nyúlnak, míg Kruskal algoritmusa úgy választja ki az éleket, hogy az él helyzete ne az utolsó lépésen alapuljon.
• A prim algoritmusában a gráfnak összekapcsolt gráfnak kell lennie, míg a Kruskal-féle szétkapcsolott gráfokon is működhet.
• Prim algoritmusának időbeli összetettsége O (V 2), Kruskal időbeli összetettsége pedig O (logV).
