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

Kruskal vs Prim

A számítástechnikában Prim és Kruskal algoritmusok egy kapzsi algoritmus, amely minimális átfogó fát talál a csatlakoztatott súlyozott, nem irányított gráf számára. A kiterjedő fa egy grafikon algráfja, úgy, hogy a grafikon minden egyes csomópontját egy út vezet össze, amely egy fa. Minden átfogó fa súlya van, és az átfogó fák minimális lehetséges súlya / költsége a minimális átfogó fa (MST)..

További információ Prim algoritmusáról

Az algoritmust 1930-ban Vojtěch Jarník cseh matematikus, később pedig függetlenül Robert C. Prim számítógépes tudós fejlesztette ki 1957-ben. Ezt 1959-ben Edsger Dijkstra fedezte fel. Az algoritmust három kulcsfontosságú lépésben lehet megállapítani;

Adott n csomóponttal és az egyes élek súlyával összekapcsolt gráf,

1. Válasszon 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 kapcsolt egyes élek súlyát, és válassza ki a minimumot. Adja hozzá a szélt és a csomópontot a T fa másik végéhez, és távolítsa el az élt a grafikonból. (Válasszon egyet, ha létezik kettő vagy több minimum)

3. Ismételje meg a 2. lépést, amíg n-1 élek hozzáadódnak a fához.

Ebben a módszerben a fa egyetlen tetszőleges csomóponttal kezdődik, és az egyes ciklusoktól kezdve kibővül. Ezért az algoritmus megfelelő működéséhez a gráfnak összekapcsolt gráfnak kell lennie. A Prim algoritmusának alap formája O (V²).

További információ Kruskal algoritmusáról

A Joseph Kruskal által kifejlesztett algoritmus az American Mathematical Society 1956-ban jelent meg. Kruskal algoritmusa három egyszerű lépésben is kifejezhető..

Adott grafikon n csomóponttal és az egyes élek súlya,

1. Válassza ki a teljes grafikon legkisebb súlyú ívét, adja hozzá a fához, és törölje a grafikonból.

2. A fennmaradó rész közül válassza ki a legkevesebb súlyt él, oly módon, hogy ne hozzon létre ciklust. Adja hozzá a szélt a fához, és törölje a grafikonból. (Válasszon egyet, ha létezik kettő vagy több minimum)

3. Ismételje meg a folyamatot a 2. lépésben.

Ebben a módszerben az algoritmus a legkevesebb súlyozott szélgel kezdődik, és folytatja az egyes élek kiválasztását minden ciklusonként. Ezért az algoritmusban a gráfot nem kell összekapcsolni. Kruskal algoritmusának O időbeli összetettsége van (logV)

Mi a különbség Kruskal és Prim algoritmusa között??

• Prim algoritmusa egy csomóponttal inicializálódik, míg Kruskal algoritmusa éllel kezdődik.

• Prim algoritmusai az egyik csomóponttól a másikig terjednek, míg Kruskal algoritmusa úgy választja meg az éleket, hogy a szél pozíciója nem az utolsó lépésre épül.

• A prim algoritmusában a gráfnak összekapcsolt gráfnak kell lennie, míg a Kruskal gráfoknak is lehet elválasztott gráfokon is működniük..

• Prim algoritmusának O (V²), és Kruskal időbeli összetettsége O (logV).