Kruskal vs Prim
Tietojenkäsittelytieteessä Primin ja Kruskalin algoritmit ovat ahne algoritmi, joka löytää yhdistetyn painotetun suuntaamattoman kaavion minimipinta-alan. Ylittävä puu on graafin aligrafiikka siten, että graafin kukin solmu on yhdistetty polulla, joka on puu. Jokaisella ulottuvalla puulla on paino, ja kaikkien ulottuvien puiden pienin mahdollinen paino / hinta on vähimmäispinta (MST).
Lisätietoja Primin algoritmista
Algoritmin kehitti tšekkiläinen matemaatikko Vojtěch Jarník vuonna 1930 ja myöhemmin itsenäisesti tietojenkäsittelytieteen tutkija Robert C. Prim vuonna 1957. Edsger Dijkstra löysi sen uudelleen vuonna 1959. Algoritmi voidaan ilmoittaa kolmessa keskeisessä vaiheessa;
Kun otetaan huomioon yhdistetty kaavio, jossa on n solmua ja kunkin reunan vastaava paino, 1. Valitse mielivaltainen solmu kaaviosta ja lisää se puuhun T (joka on ensimmäinen solmu)
2. Harkitse kunkin puun solmuihin liitetyn reunan painot ja valitse minimi. Lisää reuna ja solmu puun T toiseen päähän ja poista reuna kaaviosta. (Valitse mikä tahansa, jos minimiä on vähintään kaksi)
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. Näin ollen, jotta algoritmi toimisi kunnolla, kaavion on oltava yhdistetty kaavio. Perusmuoto on Primin algoritmi on aikakompleksisuus O (V 2).
Lisätietoja Kruskalin algoritmista
Joseph Kruskalin kehittämä algoritmi ilmestyi American Mathematical Societyn julkaisuissa vuonna 1956. Kruskalin algoritmi voidaan ilmaista myös kolmessa yksinkertaisessa vaiheessa.
Kun otetaan huomioon kaavio, jossa on n solmua ja kunkin reunan vastaava paino, 1. Valitse kaari, jolla on pienin paino koko kaaviosta, lisää puu ja poista kaaviosta.
2. Valitse jäljellä olevista vähiten painotettu reuna tavalla, joka ei muodosta jaksoa. Lisää reuna puuhun ja poista kaaviosta. (Valitse mikä tahansa, jos minimiä on vähintään kaksi)
3. Toista prosessi vaiheessa 2.
Tässä menetelmässä algoritmi alkaa pienimmällä painotetulla reunalla ja jatkaa kunkin reunan valitsemista jokaisessa jaksossa. Siksi algoritmissa kuvaajan ei tarvitse olla kytkettynä. Kruskalin algoritmilla on aikakompleksisuus O (logV)
Mikä on ero Kruskalin ja Primin algoritmin välillä?
• Primin algoritmi alustetaan solmulla, kun taas Kruskalin algoritmi alkaa reunalla.
• Primin algoritmit ulottuvat solmusta toiseen, kun taas Kruskalin algoritmi valitsee reunat siten, että reunan sijainti ei perustu viimeiseen vaiheeseen.
• Primin algoritmissa kuvaajan on oltava kytketty graafi, kun taas Kruskalin voi toimia myös irti kytketyissä kuvaajissa.
• Primin algoritmin aikakompleksi on O (V 2), ja Kruskalin aikakompleksisuus on O (logV).
