Atšķirība starp Kruskal un Prim

Kruskal vs Prim

Datorzinātnē Prim un Kruskal algoritmi ir mantkārīgs algoritms, kas atrod minimālo aptverošo koku savienotajam svērtajam, nenovirzītajam grafam. Aptverošais koks ir grafika apakšgrāfs, kurā katrs grafika mezgls ir savienots ar ceļu, kas ir koks. Katram stiepjošajam kokam ir svars, un visu stiepjošo koku minimālais iespējamais svars / izmaksas ir minimālais stiepjošais koks (MST)..

Vairāk par Prim's algoritmu

Algoritmu 1930. gadā izstrādāja čehu matemātiķis Vojtěch Jarník, vēlāk 1957. gadā patstāvīgi - datorzinātnieks Roberts C. Prim. To 1959. gadā no jauna atklāja Edsger Dijkstra. Algoritmu var izteikt trīs galvenajos posmos;

Ņemot vērā savienoto grafiku ar n mezgliem un katras malas atbilstošo svaru,

1. Atlasiet patvaļīgu mezglu no diagrammas un pievienojiet to kokam T (tas būs pirmais mezgls).

2. Apsveriet katras malas svaru, kas savienots ar mezglā esošajiem mezgliem, un atlasiet minimālo. Pievienojiet malu un mezglu T otrā koka galā un noņemiet malu no diagrammas. (Atlasiet jebkuru, ja pastāv divi vai vairāki minimumi)

3. Atkārtojiet 2. darbību, līdz kokam ir pievienotas n-1 malas.

Šajā metodē koks sākas ar vienu patvaļīgu mezglu un ar katru ciklu izplešas no šī mezgla uz priekšu. Tātad, lai algoritms darbotos pareizi, diagrammai jābūt savienotai diagrammai. Prima algoritma pamatformai laika sarežģītība ir O (V²).

Vairāk par Kruskal algoritmu

Džozefa Kruskala izstrādātais algoritms parādījās Amerikas Matemātikas biedrības darbos 1956. gadā. Kruskal algoritmu var izteikt arī trīs vienkāršās darbībās.

Ņemot grafiku ar n mezgliem un katras malas atbilstošo svaru,

1. Atlasiet loka ar vismazāko visa grafika svaru, pievienojiet kokam un izdzēsiet no diagrammas.

2. No atlikušajām izvēlieties vismazāk svērto malu tādā veidā, kas neveido ciklu. 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 vismazāk svērto malu un turpina atlasīt katru malu katrā ciklā. Tāpēc algoritmā diagramma nav jāsavieno. Kruskal algoritmam ir laika sarežģītība O (logV)

Kāda ir atšķirība starp Kruskal un Prima algoritmu?

• Prima algoritms tiek inicializēts ar mezglu, savukārt Kruskal algoritms sākas ar malu.

• Prima algoritmi iet no viena mezgla uz otru, kamēr Kruskal algoritms malas izvēlas tā, lai malas atrašanās vieta netiktu balstīta uz pēdējo soli..

• Prim algoritmā grafikam jābūt savienotam grafam, kamēr Kruskal's var darboties arī atvienotos grafikos..

• Prima algoritmam laika sarežģītība ir O (V²), un Kruskal laika sarežģītība ir O (logV).