Különbség Kruskal és Prim Között

2024 Szerző: Mildred Bawerman | [email protected]. Utoljára módosítva: 2023-12-16 08:39

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 ²).

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 ²), Kruskal időbeli összetettsége pedig O (logV).