Kruskal vs Prim
Sa computer science, ang Prim's at Kruskal's algorithm ay isang greedy algorithm na nakakahanap ng minimum spanning tree para sa isang konektadong weighted undirected graph. Ang spanning tree ay isang subgraph ng isang graph na ang bawat node ng graph ay konektado ng isang path, na isang puno. Ang bawat spanning tree ay may timbang, at ang pinakamababang posibleng timbang/gastos ng lahat ng spanning tree ay ang minimum spanning tree (MST).
Higit pa tungkol sa Prim’s Algorithm
Ang algorithm ay binuo ng Czech mathematician na si Vojtěch Jarník noong 1930 at nang maglaon ay nakapag-iisa ng computer scientist na si Robert C. Prim noong 1957. Ito ay muling natuklasan ni Edsger Dijkstra noong 1959. Ang algorithm ay maaaring sabihin sa tatlong mahahalagang hakbang;
Dahil sa konektadong graph na may n node at kaukulang bigat ng bawat gilid, 1. Pumili ng arbitrary na node mula sa graph at idagdag ito sa tree T (na magiging unang node)
2. Isaalang-alang ang mga bigat ng bawat gilid na konektado sa mga node sa puno at piliin ang pinakamababa. Idagdag ang gilid at ang node sa kabilang dulo ng tree T at alisin ang gilid mula sa graph. (Pumili ng anuman kung may dalawa o higit pang minimum)
3. Ulitin ang hakbang 2, hanggang sa maidagdag ang n-1 na gilid sa puno.
Sa paraang ito, ang puno ay nagsisimula sa isang arbitrary na node at lumalawak mula sa node na iyon pataas sa bawat cycle. Samakatuwid, para gumana nang maayos ang algorithm, kailangang konektadong graph ang graph. Ang pangunahing anyo ng algorithm ng Prim ay may time complexity na O(V2)..
Higit pa tungkol sa Algorithm ng Kruskal
Ang algorithm na binuo ni Joseph Kruskal ay lumabas sa mga paglilitis ng American Mathematical Society noong 1956. Ang algorithm ng Kruskal ay maaari ding ipahayag sa tatlong simpleng hakbang.
Ibinigay ang graph na may n node at kaukulang bigat ng bawat gilid, 1. Piliin ang arko na may pinakamaliit na bigat ng buong graph at idagdag sa tree at tanggalin mula sa graph.
2. Sa natitira, piliin ang hindi bababa sa timbang na gilid, sa paraang hindi bumubuo ng cycle. Idagdag ang gilid sa puno at tanggalin mula sa graph. (Pumili ng anuman kung may dalawa o higit pang minimum)
3. Ulitin ang proseso sa hakbang 2.
Sa paraang ito, nagsisimula ang algorithm sa pinakamababang timbang na gilid at patuloy na pinipili ang bawat gilid sa bawat cycle. Samakatuwid, sa algorithm ang graph ay hindi kailangang konektado. Ang algorithm ng Kruskal ay may time complexity ng O(logV)
Ano ang pagkakaiba ng Kruskal’s at Prim’s Algorithm?
• Nagsisimula ang algorithm ng Prim sa isang node, samantalang ang algorithm ng Kruskal ay nagsisimula sa isang gilid.
• Ang mga algorithm ng Prim ay sumasaklaw mula sa isang node patungo sa isa pa habang pinipili ng algorithm ng Kruskal ang mga gilid sa paraang hindi nakabatay ang posisyon ng gilid sa huling hakbang.
• Sa algorithm ng prim, ang graph ay dapat na konektadong graph habang ang Kruskal ay maaaring gumana rin sa mga nakadiskonektang graph.
• Ang algorithm ng Prim ay may time complexity na O(V2), at ang time complexity ng Kruskal ay O(logV).
