Ero Kruskalin ja Prim n välillä

Kruskal vs Prim

Tietotekniikassa Primin ja Kruskalin algoritmit ovat ahne algoritmeja, jotka löytävät kytketyn painotetun suuntaamattoman kuvaajan vähimmäisalueen. Leveävä puu on osa kuvaajaa, joka kuvaajan jokaista solmua yhdistää polulla, joka on puu. Jokaisella ulottuvalla puulla on paino, ja kaikkien ulottuvien puiden pienin mahdollinen paino / hinta on pienin ulottuva puu (MST)..

Lisätietoja Primin algoritmista

Tšekin matemaatikko Vojtěch Jarník kehitti algoritmin vuonna 1930 ja myöhemmin itsenäisesti tietotekniikan tutkija Robert C. Prim vuonna 1957. Edsger Dijkstra löysi sen uudelleen. Algoritmi voidaan sanoa kolmessa avainvaiheessa;

Annetaan kytketty kuvaaja, jossa on n solmua ja kunkin reunan vastaava paino,

1. Valitse mielivaltainen solmu kuvaajasta ja lisää se puuhun T (joka on ensimmäinen solmu)

2. Harkitse puun solmuihin kytketyn kunkin reunan painot ja valitse minimi. Lisää reuna ja solmu puun T toiseen päähän ja poista reuna kaaviosta. (Valitse mikä tahansa, jos vähintään kaksi minimiä on olemassa)

3. Toista vaihe 2, kunnes puuhun lisätään n-1 reunaa.

Tässä menetelmässä puu alkaa yhdellä mielivaltaisella solmulla ja laajenee siitä solmusta eteenpäin jokaisen jakson aikana. Siksi, jotta algoritmi toimisi kunnolla, kuvaajan on oltava kytketty kuvaaja. Prim-algoritmin perusmuodolla on ajan monimutkaisuus O (V²).

Lisätietoja Kruskalin algoritmista

Joseph Kruskalin kehittämä algoritmi ilmestyi American Mathematical Society -julkaisussa vuonna 1956. Kruskalin algoritmi voidaan ilmaista myös kolmella yksinkertaisella vaiheella.

Annetaan kuvaaja, jossa on n solmua ja kunkin reunan vastaava paino,

1. Valitse kaari, jolla on koko kuvaajan vähiten paino, lisää puu ja poista kaaviosta.

2. Valitse jäljelle jäävistä vähiten painotetusta reunasta tavalla, joka ei muodosta sykliä. Lisää puun reuna ja poista kaaviosta. (Valitse mikä tahansa, jos vähintään kaksi minimiä on olemassa)

3. Toista vaihe 2.

Tässä menetelmässä algoritmi alkaa vähiten painotetulla reunalla ja jatkaa kunkin reunan valintaa jokaisessa jaksossa. Siksi graafia ei tarvitse algoritmissa yhdistää. Kruskalin algoritmissa on aikakompleksisuus O (logV)

Mitä eroa on Kruskalin ja Primin algoritmissa??

• Primin algoritmi alkaa solmulla, kun taas Kruskalin algoritmi aloittaa reunalla.

• Primin algoritmit ulottuvat solmusta toiseen, kun taas Kruskalin algoritmi valitsee reunat siten, että reunan sijainti ei perustu viimeiseen vaiheeseen.

• Prim-algoritmissa kuvaajan on oltava kytketty kuvaaja, kun taas Kruskalin voi toimia myös irrotetussa kuvaajassa..

• Primin algoritmissa aikakompleksi on O (V²), ja Kruskalin aikakompleksi on O (logV).