Kruskal vs Prim
Kompiuterių moksle Prim ir Kruskal algoritmai yra gobšus algoritmas, kuris randa susieto svertinio nenukreipto grafo minimalų apimantį medį. Apimamasis medis yra grafo pografis, kuriame kiekvienas grafiko mazgas yra sujungtas keliu, kuris yra medis. Kiekvienas besitęsiantis medis turi svorį, o mažiausias visų besitęsiančių medžių svoris / kaina yra mažiausias apimantis medis (MST).
Daugiau apie Prim algoritmą
Algoritmą 1930 m. sukūrė čekų matematikas Vojtěchas Jarníkas, o vėliau savarankiškai 1957 m. kompiuterių mokslininkas Robertas C. Primas. 1959 m. jį iš naujo atrado Edsgeris Dijkstra. Algoritmą galima nurodyti trimis pagrindiniais žingsniais;
Atsižvelgiant į sujungtą grafiką su n mazgų ir atitinkamą kiekvienos briaunos svorį, 1. Pasirinkite savavališką mazgą iš grafiko 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 gale T ir pašalinkite kraštą iš grafiko. (Pasirinkite bet kurį, jei yra du ar daugiau minimumų)
3. Kartokite 2 veiksmą, kol prie medžio bus pridėta n-1 briaunų.
Šiuo metodu medis prasideda nuo vieno savavališko mazgo ir plečiasi nuo to mazgo su kiekvienu ciklu. Taigi, kad algoritmas veiktų tinkamai, grafikas turi būti sujungtas grafikas. Pagrindinės Prim algoritmo formos laiko sudėtingumas yra O(V2).
Daugiau apie Kruskal algoritmą
Joseph Kruskal sukurtas algoritmas pasirodė Amerikos matematikų draugijos darbuose 1956 m. Kruskal algoritmą taip pat galima išreikšti trimis paprastais žingsniais.
Atsižvelgiant į grafiką su n mazgų ir atitinkamą kiekvieno krašto svorį, 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ą taip, kad nebūtų sudarytas ciklas. Pridėkite kraštą prie medžio ir ištrinkite iš grafiko. (Pasirinkite bet kurį, jei yra du ar daugiau minimumų)
3. Pakartokite 2 veiksmą.
Šiuo metodu algoritmas prasideda nuo mažiausiai svertinio krašto ir toliau pasirenka kiekvieną kraštą kiekviename cikle. Todėl algoritme grafo jungti nereikia. Kruskal algoritmo laiko sudėtingumas yra O(logV)
Kuo skiriasi Kruskal ir Prim algoritmas?
• Prim algoritmas inicijuojamas naudojant mazgą, o Kruskal algoritmas pradedamas naudojant briauną.
• Prim algoritmai apima nuo vieno mazgo iki kito, o Kruskal algoritmas parenka briaunas taip, kad krašto padėtis nebūtų pagrįsta paskutiniu žingsniu.
• Taikant „Prim“algoritmą, grafikas turi būti sujungtas grafikas, o Kruskal gali veikti ir atjungtuose grafikuose.
• Prim algoritmo laiko sudėtingumas yra O(V2), o Kruskal laiko sudėtingumas yra O(logV).
