Erinevus Kruskali ja Primi vahel

Kruskal vs Prim

Arvutiteaduses on Prim'i ja Kruskali algoritmid ahne algoritm, mis leiab ühendatud kaalutud suunamata graafi jaoks minimaalse katvuspuu. Ulatuslik puu on graafi alamgraaf, nii et iga graafi sõlm on ühendatud teega, milleks on puu. Igal toestaval puul on kaal ja kõigi kattepuude minimaalne võimalik kaal / maksumus on minimaalne kattepuu (MST).

Lisateave Prim'i algoritmi kohta

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

Arvestades ühendatud graafikut n sõlmega ja iga serva vastavat kaalu,

1. Valige graafikult suvaline sõlm ja lisage see puu T (see on esimene sõlm)

2. Mõelge puus olevate sõlmedega ühendatud iga serva kaalule ja valige minimaalne. Lisage serv ja sõlm puu T teises otsas ja eemaldage serv graafikult. (Valige kaks või enam miinimumi)

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

Selle meetodi korral algab puu ühe suvalise sõlmega ja laieneb sellest tsüklist alates iga tsükliga. Seega peab algoritmi nõuetekohaseks toimimiseks olema graaf ühendatud graafik. Prim'i algoritmi põhivormi ajaline keerukus on O (V²).

Lisateavet Kruskali algoritmi kohta

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

Antud graafikul on n sõlme ja iga serva vastav mass,

1. Valige kaar kogu graafiku väikseima kaaluga, lisage puu ja kustutage graafikult.

2. Ülejäänud hulgast valige kõige vähem kaalutud serv viisil, mis ei moodusta tsüklit. Lisage puu serv ja kustutage graafikust. (Valige kaks või enam miinimumi)

3. Korrake sammu 2 toimingut.

Selle meetodi korral algab algoritm kõige vähem kaalutud servaga ja jätkub iga serva valimine igas tsüklis. Seetõttu ei pea graafikut algoritmis ühendama. Kruskali algoritmil on aja keerukus O (logV)

Mis vahe on Kruskali ja Prim'i algoritmil?

• Primsi algoritm initsieeritakse sõlmega, Kruskali algoritm aga servaga.

• Primsi algoritmid ulatuvad ühest sõlmest teise, samal ajal kui Kruskali algoritm valib servad viisil, et serva asukoht ei põhine viimasel sammul.

• Prim'i algoritmis peab graaf olema ühendatud graaf, samas kui Kruskal võib toimida ka lahtiühendatud graafikutel..

• Primsi algoritmil on aja keerukus O (V²) ja Kruskali ajaline keerukus on O (logV).