piatok, 24 mája, 2024
HomeSlovníkIT slovníkPrimov algoritmus

Primov algoritmus

Čo je to Primov algoritmus?

Primov algoritmus je algoritmus na hľadanie minimálneho rozťažného stromu v ohodnotenom grafe, čo je stromový podgraf, ktorý obsahuje všetky vrcholy pôvodného grafu. Tento algoritmus sa využíva na nájdenie najmenej nákladnej cesty, ktorá spojí všetky vrcholy grafu tak, aby neobsahovala žiadne cykly a celková váha hrán bola čo najmenšia. Primov algoritmus začína s jedným náhodným vrcholom a postupne pridáva najlacnejšie hrany, ktoré ešte nezahŕňajú žiadny cyklus, až kým nie sú spojené všetky vrcholy grafu.

Tento algoritmus je tiež typom „greedy“ algoritmu, ktorý znamená, že sa v každom kroku snaží minimalizovať celkovú váhu kostry a zabezpečiť, aby každý vrchol bol pripojený do stromu. Primov algoritmus sa často používa v sieťových a logistických aplikáciách, kde je potrebné nájsť optimálnu cestu alebo sieť s minimálnymi nákladmi.

Ďalšie termíny z IT slovníka

Pridajte komentár

Please enter your comment!
Please enter your name here