Kruskalin ja Primin algoritmien vertailu pienimmän virittävän puun etsimisessä

Abstract

Graafiteoria on matematiikan osa-alue, jota hyödynnetään laajasti useilla muilla tieteenaloilla. Virittävät puut ovat osa graafiteoriaa. Virittäviä puita käytetään usein suunnittelun apuna, sillä reaalimaailman asioita voidaan monesti mallintaa graafien avulla. Pienimpiä virittäviä puita etsitään graafeista algoritmien avulla ja niiden löytämiseen on tarjolla useita eri algoritmeja. Tässä työssä tutkittiin ja vertailtiin kahta pienimmän virittävän puun etsimiseen käytettyä Kruskalin algoritmia ja Primin algoritmia. Ohjelmoitujen algoritmien tehokkuuksia sekä toteutuksia tutkittiin ja vertailtiin toisiinsa tarkoituksena selvittää niiden tehokkuutta pienintä virittävää puuta etsittäessä eri kokoisissa graafeissa. Molempien algoritmitien asymptoottinen tehokkuus vastasi odotettua asymptoottista tehokkuutta. Lisäksi molemmat algoritmit olivat mahdollisia toteuttaa käyttämällä C++-ohjelmointikielen standardikirjastoa ja standardikirjaston sisältämiä tietorakenteita. Tehokkuuksia vertailtaessa Kruskalin algoritmi oli tehokkaampi kuin Primin algoritmi kaikissa tilanteissa. Lisäksi Kruskalin algoritmin optimaalinen toteuttaminen oli helpompaa kuin Primin, joka olisi vaatinut joko kolmannen osapuolen kirjastoja tai oman prioriteettijonon toteuttamista.