Skirtumas tarp Kruskal ir Prim

„Kruskal vs Prim“

Kompiuterių moksle Primo ir Kruskalo algoritmai yra gobšus algoritmas, kuris suranda mažiausią jungiamojo svertinio nejudamo grafiko medį. Aprėpiantis medis yra grafiko pogrupis, toks, kad kiekvienas grafiko mazgas yra sujungtas keliu, kuris yra medis. Kiekvienas besiribojantis medis turi savo svorį, o mažiausias įmanomas visų besiribojančių medžių svoris / kaina yra mažiausias įtempiantis medis (MST)..

Daugiau apie Prim algoritmą

Algoritmą sukūrė čekų matematikas Vojtěch Jarník 1930 m., O vėliau savarankiškai - informatikas Robertas C. Prim. 1957 m. - 1959 m. Jį atrado Edsgeris Dijkstra.

Pateiktas sujungtas grafikas su n mazgais ir atitinkamas kiekvieno krašto svoris,

1. Iš diagramos pasirinkite savavališką mazgą ir pridėkite jį prie medžio T (kuris bus pirmasis mazgas)

2. Apsvarstykite kiekvieno krašto, sujungto su medžio mazgais, svorius ir pasirinkite mažiausią. Pridėkite kraštą ir mazgą kitame medžio T gale ir nuimkite kraštą nuo grafiko. (Pasirinkite bet kurį, jei yra du ar daugiau minimumų)

3. Pakartokite 2 veiksmą, kol prie medžio bus pridėta n-1 briaunų.

Taikant šį metodą, medis prasideda nuo vieno savavališko mazgo ir plečiasi nuo to mazgo kiekvienu ciklu. Taigi, kad algoritmas tinkamai veiktų, grafikas turi būti sujungtas. Pagrindinė Primo algoritmo forma turi laiko sudėtingumą O (V²).

Daugiau apie Kruskalio algoritmą

Joseph Kruskal sukurtas algoritmas pasirodė 1956 m. Amerikos matematikų draugijos leidinyje. Kruskal algoritmą taip pat galima išreikšti trim paprastais žingsniais..

Pateiktas grafikas su n mazgais ir atitinkamas kiekvieno krašto svoris,

1. Pasirinkite lanką su mažiausiu viso grafiko svoriu, pridėkite prie medžio ir ištrinkite iš grafiko.

2. Iš likusių kraštų pasirinkite mažiausiai sveriamą kraštą taip, kad nesudarytumėte ciklo. Pridėkite medžio briauną ir ištrinkite iš diagramos. (Pasirinkite bet kurį, jei yra du ar daugiau minimumų)

3. Pakartokite 2 veiksme nurodytą procesą.

Taikant šį metodą, algoritmas pradedamas nuo mažiausiai sveriamo krašto ir toliau pasirenkamas kiekvienas kraštas kiekviename cikle. Todėl algoritme grafiko nereikia sujungti. Kruskalio algoritmas turi laiko sudėtingumą O (logV)

Kuo skiriasi Kruskalio ir Primo algoritmai?

• Primo algoritmas inicijuojamas mazgu, o Kruskalio algoritmas inicijuojamas briauna.

• Primo algoritmai pereina iš vieno mazgo į kitą, o Kruskalio algoritmas pasirenka kraštus taip, kad krašto padėtis nebūtų pagrįsta paskutiniu žingsniu..

• Prim algoritme grafikas turi būti sujungtas grafikas, tuo tarpu „Kruskal“ gali veikti ir atjungtuose grafikuose..

• Primo algoritmas turi laiko sudėtingumą O (V²), o Kruskalio laiko sudėtingumas yra O (logV).