Harjoitukset viikkoharjoitussessioon 13¶

Tehtävä 1¶

Graafin virittävä puu (a spanning tree for a graph) on graafin kaarien osajoukko, joka yhdistää kaikki solmut ja muodostaa puun, eli tulos ei sisällä silmukoita (cycles). Yhdelle graafille on tyypillisesti monia mahdollisia virittäviä puita. Pienin virittävä puu (minimal spanning tree) on puu, jossa sen kaarien painojen summa on pienin. Pienin virittävä puu on hyödyllinen, jos on tarve minimoida kokonaiskustannus, eli luoda halvin mahdollinen graafi, jossa voi vielä tavoittaa kaikki solmut. Tällaisia ongelmia voit tavata esimerkiksi viestintäverkkojen konfiguroinnin ja rakentamisen yhteydessä.

Kruskalin algoritmi on yksi tapa luoda pienin virittävä puu. Lue algoritmista enlanninkielisestä Wikipedia-artikkelista Kruskal’s algorithm . Miten algoritmi toimii ja luo pienimmän virittävän puun? Huomaatko, miksi se luo nimenomaan pienimmän virittävän puun? Voit myös katsoa visualisoinnin algoritmista. (Kruskalin algoritmi toimii myös, jos graafi ei ole yhdistetty. Tällöin se luo automaattisesti joukon virittäviä puita, eli metsän.)

Suorita Kruskalin algoritmi alla olevalle graafille.