Kruskal vs Prim
Informatikos srityje Prim ir Kruskalo algoritmai yra godus algoritmas, kuris suranda minimalų jungiamojo svertinio ir nenukreipto grafiko tarpatramį. Besidriekiantis medis yra grafiko pogrupis, kuriame kiekvienas grafo mazgas yra sujungtas keliu, kuris yra medis. Kiekvienas besidriekiantis medis turi svorį, o mažiausias galimas visų besidriekiančių medžių svoris / kaina yra mažiausias tarpatramstis (MST).
Daugiau apie „Prim“algoritmą
Algoritmą 1930 m. Sukūrė čekų matematikas Vojtěchas Jarníkas, o vėliau 1957 m. Savarankiškai - informatikas Robertas C. Primas. 1959 m. Jį iš naujo atrado Edsgeris Dijkstra. Algoritmą galima nurodyti trimis pagrindiniais žingsniais;
Atsižvelgiant į sujungtą grafiką su n mazgais ir atitinkamu kiekvieno krašto svoriu, 1. Iš grafiko 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, svorį ir pasirinkite mažiausią. Pridėkite kraštą ir mazgą kitame medžio T gale ir pašalinkite kraštą iš grafiko. (Pasirinkite bet kurį, jei yra du ar daugiau minimumų)
3. Pakartokite 2 veiksmą, kol n-1 kraštai bus pridėti prie medžio.
Taikant šį metodą, medis prasideda nuo vieno savavališko mazgo ir plečiasi nuo to mazgo toliau su kiekvienu ciklu. Taigi norint, kad algoritmas veiktų tinkamai, grafikas turi būti sujungtas. Pagrindinė Primo algoritmo forma turi O (V 2) laiko sudėtingumą.
Daugiau apie Kruskalio algoritmą
Josepho Kruskalio sukurtas algoritmas pasirodė Amerikos matematikos draugijos darbe 1956 m. Kruskalio algoritmą taip pat galima išreikšti trimis paprastais žingsniais.
Atsižvelgiant į grafiką su n mazgais ir atitinkamu kiekvieno krašto svoriu, 1. Pasirinkite lanką su mažiausiu viso grafiko svoriu ir pridėkite prie medžio ir ištrinkite iš grafiko.
2. Iš likusių pasirinkite mažiausiai svertinį kraštą tokiu būdu, kuris nesudaro ciklo. Pridėkite kraštą prie medžio ir ištrinkite iš diagramos. (Pasirinkite bet kurį, jei yra du ar daugiau minimumų)
3. Pakartokite procesą atlikdami 2 veiksmą.
Taikant šį metodą, algoritmas pradedamas nuo mažiausio svertinio krašto ir toliau renkamas kiekvienas kraštas kiekviename cikle. Todėl algoritme grafo nereikia prijungti. Kruskalio algoritmas turi laiko sudėtingumą O (logV)
Kuo skiriasi Kruskalio ir Primo algoritmas?
• „Prim“algoritmas inicijuojamas mazgu, o „Kruskal“- su kraštu.
• „Prim“algoritmai tęsiasi nuo vieno mazgo iki kito, o „Kruskal“algoritmas parenka kraštus taip, kad krašto padėtis nebūtų pagrįsta paskutiniu žingsniu.
• „Prim“algoritme grafikas turi būti prijungtas, o „Kruskal“gali veikti ir atjungtuose grafikuose.
• Prim algoritmo laiko sudėtingumas yra O (V 2), o Kruskalo laiko sudėtingumas yra O (logV).
