minimumipuualgoritmeja

Minimumipuualgoritmeja ovat tietojenkäsittelytieteessä käytettyjä algoritmeja, joiden tavoitteena on löytää painoltaan pienin mahdollinen puu, joka yhdistää kaikki annetun graafin solmut. Tällainen puu tunnetaan nimellä minimipuu. Graafi, josta minimipuu etsitään, on painotettu ja kytketty. Minimipuu muodostaa osajoukosta graafin kaaria, jotka muodostavat puun ja joiden kaikkien painojen summa on pienin mahdollinen.

Tunnetuimpia minimipuu-algoritmeja ovat Kruskalin algoritmi ja Primin algoritmi. Kruskalin algoritmi toimii lisäämällä graafin kaaria järjestyksessä pienimmästä suurimpaan, kunhan lisäys ei muodosta sykliä. Primin algoritmi puolestaan aloittaa yhdestä solmusta ja kasvattaa minimipuuta lisäämällä siihen aina uusi, pienimmän painon omaava kaari, joka yhdistää puuhun jo kuuluvan solmun puuhun vielä kuulumattomaan solmuun. Molemmat algoritmit takaavat optimaalisen ratkaisun eli löytävät todellisen minimipuun.

Minimipuu-algoritmeilla on lukuisia sovelluksia käytännössä. Niitä voidaan hyödyntää esimerkiksi sähköverkon suunnittelussa tehokkaimman reitityksen löytämiseksi, tietoliikenneverkkojen rakentamisessa tai polkujen etsimisessä verkostoissa. Ongelman ydin on löytää kustannustehokkain tapa yhdistää joukko pisteitä toisiinsa.