Kruskal vs Prim
Tietojenkäsittelytieteessä Primin ja Kruskalin algoritmit ovat ahneita algoritmeja, jotka löytävät minimivirittävän puun yhdistetylle painotetulle suuntaamattomalle graafille. Virittävä puu on graafin aligraafi, jossa jokainen graafin solmu on yhdistetty polulla, joka on puu. Jokaisella virittävällä puulla on paino, ja kaikkien virittävien puiden pienin mahdollinen paino/kustannus on pienin virittävä puu (MST).
Lisätietoja Primin algoritmista
Algoritmin kehitti tšekkiläinen matemaatikko Vojtěch Jarník vuonna 1930 ja myöhemmin itsenäisesti tietojenkäsittelytieteilijä Robert C. Prim vuonna 1957. Edsger Dijkstra löysi sen uudelleen vuonna 1959. Algoritmi voidaan esittää kolmessa avainvaiheessa;
Kun yhdistetty graafi, jossa on n solmua ja kunkin reunan vastaava paino, 1. Valitse mieliv altainen solmu kaaviosta ja lisää se puuhun T (joka on ensimmäinen solmu)
2. Harkitse jokaisen puun solmuihin liitetyn reunan painoja ja valitse minimi. Lisää reuna ja solmu puun T toiseen päähän ja poista reuna graafista. (Valitse mikä tahansa, jos vähintään kaksi vähimmäisarvoa on olemassa)
3. Toista vaihe 2, kunnes n-1 reunaa on lisätty puuhun.
Tässä menetelmässä puu alkaa yhdestä mieliv altaisesta solmusta ja laajenee siitä solmusta eteenpäin jokaisen jakson yhteydessä. Siksi, jotta algoritmi toimisi oikein, kaavion on oltava yhdistetty graafi. Primin algoritmin perusmuodon aikamonimutkaisuus on O(V2).
Lisätietoja Kruskalin algoritmista
Joseph Kruskalin kehittämä algoritmi ilmestyi American Mathematical Societyn työssä vuonna 1956. Kruskalin algoritmi voidaan myös ilmaista kolmessa yksinkertaisessa vaiheessa.
Kun kaaviossa on n solmua ja kunkin reunan vastaava paino, 1. Valitse kaari, jolla on pienin paino koko kuvaajasta ja lisää se puuhun ja poista kuvaajasta.
2. Valitse lopuista vähiten painotettu reuna tavalla, joka ei muodosta sykliä. Lisää reuna puuhun ja poista kaaviosta. (Valitse mikä tahansa, jos vähintään kaksi vähimmäisarvoa on olemassa)
3. Toista vaihe 2.
Tässä menetelmässä algoritmi alkaa vähiten painotetulla reunalla ja jatkaa kunkin reunan valitsemista jokaisessa syklissä. Siksi graafia ei algoritmissa tarvitse yhdistää. Kruskalin algoritmin aikamonimutkaisuus on O(logV)
Mitä eroa on Kruskalin ja Primin algoritmilla?
• 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 graafin on oltava yhdistetty graafi, kun taas Kruskalin graafit voivat toimia myös irrotetuissa kaavioissa.
• Primin algoritmin aikamonimutkaisuus on O(V2), ja Kruskalin aikamonimutkaisuus on O(logV).
