Kruskali ja Primi erinevus

Kruskali ja Primi erinevus
Kruskali ja Primi erinevus

Video: Kruskali ja Primi erinevus

Video: Kruskali ja Primi erinevus
Video: Lööktrellide erinevus 2024, November
Anonim

Kruskal vs Prim

Arvutiteaduses on Primi ja Kruskali algoritmid ahne algoritm, mis leiab ühendatud kaalutud suunamata graafiku jaoks minimaalse ulatuva puu. Ulatuspuu on graafi alamgraaf, nii et iga graafi sõlm on ühendatud teega, mis on puu. Igal ulatuval puul on kaal ja kõigi toestavate puude minimaalne võimalik kaal/kulu on minimaalne ulatuspuu (MST).

Lisateavet Primi algoritmi kohta

Algoritmi töötas välja Tšehhi matemaatik Vojtěch Jarník 1930. aastal ja hiljem iseseisv alt arvutiteadlane Robert C. Prim 1957. aastal. Edsger Dijkstra avastas selle uuesti 1959. aastal. Algoritmi saab esitada kolmes võtmeetapis;

Arvestades n sõlmega ühendatud graafikut ja iga serva vastavat kaalu, 1. Valige graafikult suvaline sõlm ja lisage see puusse T (mis on esimene sõlm)

2. Võtke arvesse iga puu sõlmedega ühendatud serva raskust ja valige miinimum. Lisa serv ja sõlm puu teises otsas T ning eemalda serv graafikult. (Kui on kaks või enam miinimumi, valige ükskõik milline)

3. Korrake 2. sammu, kuni puule on lisatud n-1 serva.

Selle meetodi puhul algab puu ühe suvalise sõlmega ja laieneb sellest sõlmest iga tsükliga edasi. Seega, et algoritm korralikult töötaks, peab graafik olema ühendatud graafik. Primi algoritmi põhivormi ajaline keerukus on O(V2).

Lisateavet Kruskali algoritmi kohta

Joseph Kruskali välja töötatud algoritm ilmus Ameerika Matemaatika Seltsi toimetistes 1956. aastal. Kruskali algoritmi saab väljendada ka kolme lihtsa sammuga.

Arvestades n sõlmega graafikut ja iga serva vastavat kaalu, 1. Valige kogu graafiku väikseima raskusega kaar ja lisage puusse ja kustutage graafikult.

2. Ülejäänud hulgast valige kõige vähem kaalutud serv viisil, mis ei moodusta tsüklit. Lisage puule serv ja kustutage graafikult. (Kui on kaks või enam miinimumi, valige ükskõik milline)

3. Korrake toimingut punktis 2.

Selle meetodi puhul algab algoritm vähima kaalutud servaga ja jätkab iga serva valimist igas tsüklis. Seetõttu ei pea graafik algoritmis olema ühendatud. Kruskali algoritmi ajaline keerukus on O(logV)

Mis vahe on Kruskali ja Primi algoritmil?

• Primi algoritm initsialiseerub sõlmega, Kruskali algoritm aga servaga.

• Primi algoritmid ulatuvad ühest sõlmest teise, samas kui Kruskali algoritm valib servad nii, et serva asukoht ei põhine viimasel sammul.

• Primi algoritmis peab graafik olema ühendatud graaf, samas kui Kruskal saab toimida ka lahtiühendatud graafikutel.

• Primi algoritmi ajaline keerukus on O(V2) ja Kruskali ajaline keerukus on O(logV).

Soovitan: