Kruskal vs Prim
Datorzinātnēs Prim un Kruskal algoritmi ir mantkārīgs algoritms, kas atrod minimālo aptverošo koku savienotam svērtam nevirzītam grafikam. Aptverošais koks ir grafa apakšgrafs, kurā katrs grafa mezgls ir savienots ar ceļu, kas ir koks. Katram aptverošajam kokam ir svars, un visu aptverošo koku minimālais iespējamais svars/izmaksas ir minimālais aptverošais koks (MST).
Vairāk par Prim algoritmu
Algoritmu 1930. gadā izstrādāja čehu matemātiķis Vojtehs Jarniks un vēlāk neatkarīgi 1957. gadā datorzinātnieks Roberts K. Prims. To no jauna atklāja Edsgers Dijkstra 1959. gadā. Algoritmu var norādīt trīs galvenajos posmos;
Ņemot vērā savienoto grafiku ar n mezgliem un katras malas attiecīgo svaru, 1. Diagrammā atlasiet patvaļīgu mezglu un pievienojiet to kokam T (kas būs pirmais mezgls)
2. Apsveriet katras ar koka mezgliem savienotās malas svarus un atlasiet 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 paplašinās no šī mezgla ar katru ciklu. Tādējādi, lai algoritms darbotos pareizi, grafikam ir jābūt savienotam grafikam. Prim algoritma pamatformai ir laika sarežģītība O(V2).
Vairāk par Kruskal algoritmu
Džozefa Kruskala izstrādātais algoritms parādījās Amerikas Matemātikas biedrības darbā 1956. gadā. Kruskala algoritmu var arī izteikt trīs vienkāršos soļos.
Ņemot vērā grafiku ar n mezgliem un katras malas attiecīgo svaru, 1. Atlasiet loku ar vismazāko svaru visā diagrammā un pievienojiet kokam un izdzēsiet no grafika.
2. No atlikušajām atlasiet vismazāk svērto malu tā, lai tas neveidotu ciklu. Pievienojiet kokam malu un izdzēsiet no grafika. (Atlasiet jebkuru, ja pastāv divi vai vairāki minimumi)
3. Atkārtojiet procesu 2. darbībā.
Šajā metodē algoritms sākas ar vismazāk svērto malu un turpina atlasīt katru malu katrā ciklā. Tāpēc algoritmā grafam nav jābūt savienotam. Kruskal algoritma laika sarežģītība ir O(logV)
Kāda ir atšķirība starp Kruskal un Prim algoritmu?
• Prim algoritms tiek inicializēts ar mezglu, savukārt Kruskal algoritms tiek inicializēts ar malu.
• Prim algoritmi aptver vienu mezglu uz otru, savukārt Kruskal algoritms atlasa malas tā, lai malas pozīcija nebūtu balstīta uz pēdējo darbību.
• Prim algoritmā grafikam ir jābūt savienotam grafikam, savukārt Kruskal var darboties arī atvienotos grafikos.
• Prim algoritma laika sarežģītība ir O(V2), un Kruskal laika sarežģītība ir O(logV).
