Kruskal vs Prim
Datorzinātnēs Prim un Kruskal algoritmi ir alkatīgs algoritms, kas atrod minimālo aptverošo koku savienotajam svērtajam nenovirzītajam grafikam. Spenējošais koks ir tāda grafika apakšgrāfs, ka katru grafa mezglu savieno ceļš, kas ir koks. Katram aptverošajam kokam ir svars, un visu iespējamo koku minimālais iespējamais svars / izmaksas ir minimālais aptverošais koks (MST).
Vairāk par Prim's algoritmu
Algoritmu izstrādāja čehu matemātiķis Vojtěch Jarník Vojtěch Jarník 1930. gadā un vēlāk patstāvīgi datorzinātnieks Roberts C. Prim 1957. gadā. To atkārtoti atklāja Edsger Dijkstra 1959. gadā. Algoritmu var norādīt trīs galvenajos soļos;
Ņemot vērā savienoto grafiku ar n mezgliem un katras malas attiecīgo svaru, 1. Grafikā atlasiet patvaļīgu mezglu un pievienojiet to kokam T (kas būs pirmais mezgls)
2. Apsveriet katras malas svaru, kas savienota ar koka mezgliem, un izvēlieties minimālo. Pievienojiet malu un mezglu koka T otrā galā un noņemiet malu no grafika. (Atlasiet jebkuru, ja pastāv divi vai vairāki minimumi)
3. Atkārtojiet 2. darbību, līdz kokam tiek pievienotas n-1 malas.
Šajā metodē koks sākas ar vienu patvaļīgu mezglu un no katra mezgla ar katru ciklu paplašinās. Tādējādi, lai algoritms darbotos pareizi, grafikam jābūt saistītam. Primas algoritma pamatformai ir laika sarežģītība O (V 2).
Vairāk par Kruskaļa algoritmu
Džozefa Kruska izstrādātais algoritms parādījās Amerikas Matemātikas biedrības lietvedībā 1956. gadā. Kruskaļa algoritmu var izteikt arī trīs vienkāršās darbībās.
Ņemot vērā diagrammu ar n mezgliem un katras malas attiecīgo svaru, 1. Atlasiet loku ar vismazāko visa grafika svaru un pievienojiet kokam un izdzēsiet no diagrammas.
2. No atlikušajiem atlasiet vismazāk svērto malu tā, lai neveidotos cikls. Pievienojiet kokam malu un izdzēsiet no diagrammas. (Atlasiet jebkuru, ja pastāv divi vai vairāki minimumi)
3. Atkārtojiet procesu 2. darbībā.
Šajā metodē algoritms sākas ar mazāko svērto malu un turpina izvēlēties katru malu katrā ciklā. Tāpēc algoritmā grafam nav jābūt savienotam. Kruskaļa algoritmam ir laika sarežģītība O (logV)
Kāda ir atšķirība starp Kruskaļa un Primas algoritmu?
• Prim algoritms tiek inicializēts ar mezglu, bet Kruskal algoritms - ar malu.
• Primas algoritmi aptver vienu mezglu no otra, savukārt Kruskaļa algoritms izvēlas malas tā, lai malas pozīcija nebūtu balstīta uz pēdējo soli.
• Prim's algoritmā grafam jābūt savienotam grafam, kamēr Kruskal var darboties arī atvienotos grafos.
• Prim algoritmam ir laika sarežģītība O (V 2), un Kruska laika sarežģītība ir O (logV).
