Minimalus dengiantis medis

Minimalus dengiantis medis

Eksperimento būdų nustatykite algoritmo sudėtingumą. Palyginkite rezultatą su teoriniu:

• parašyti programą;

• atlikti testavimą su skirtingais duomenų kiekiais;

• braižyti grafiką;

• padarykite išvadas;

Jūsų pasirinkti: Kraskalo algoritmas.

Kaskalo algoritmas

Kraskalo algoritmas (angl. Kruskal's algorithm) yra minimalių ištemptų medžių (minimal spanning tree) konstravimo algoritmas grafe. Minimalus ištemptas medis yra toks sujungtas grafas, kuris yra jungiamasis (nėra ciklų) ir jo svoris yra minimalus, t.y., suma visų briaunų svorių yra kuo mažiausia.

Pagrindiniai Kraskalo algoritmo žingsniai:

• Surūšiuot visas briaunas pagal svorį didėjimo tvarka.

• Pradėti su atskirais minimaliais ištemptais medžiai (kuriuose yra tik viena viršūnė) ir palaipsniui jungti juos su mažiausio svorio briauna, jei tai nekelia ciklų.

Grafo viršūnių skaičius 50. C++ programa matuojama rikiavimo laiką mikrosekundėmis kai briaunos – nuo 1000 iki 10000.

Rezultatai pateikiami lentelėje

Rezultatai pateikiami lentelėje

Išvados

1. Remiantis teorija, Kruskalo algoritmo sudėtingumas yra daugiausiai priklauso nuo briaunų rūšiavimo pagal svorį. Pagrindinis žingsnis, kuriame briaunos surūšiuojamos, turi sudėtingumą O(E \log E), kur E yra briaunų skaičius grafe. Tai atsiranda dėl to, kad surūšiuojant briaunas pagal svorį, dauguma efektyvių rūšiavimo algoritmų turi sudėtingumą, proporcingą $E \log E$.

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!