Kruskals algoritm är en girig algoritm för att skapa ett minimalt uppspännande träd från en godtycklig sammanhängande, viktad och oriktad graf.

Algoritmen bygger en skog av träd som allt eftersom växer ihop. Algoritmen är girig, eftersom den hela tiden lägger till den kortaste kanten den kan hitta till sina delträd.

Pseudokod Algoritmen kan beskrivas på följande sätt:

För att hitta ett minimalt uppspännande träd T i den sammanhängande grafen G Upprepa tills T innehåller alla noder i G Låt v vara den kortaste sträckan i G som inte märkts som förbrukad Märk v som förbrukad Om v inte bildar en cykel i T Lägg v till T T är ett minimalt uppspännande träd

Exempel

Bild Beskrivning200px|vänster Målet är att finna ett träd som omfattar hörnen A–G där trädets kanter har så låg sammanlagd kostnad som möjligt.200px|vänster Kanterna AD och CE är de kanter i grafen som har lägst kostnad. Vilken av kanterna som i detta steg ska läggas till trädet som utgör problemets lösning är godtyckligt, men för konsekvensens skull kan alfabetisk ordning användas. AD blir därför en del av lösningen.200px|vänster CE har samma låga kostnad och bildar inte en cykel om den läggs till problemets lösning. Den läggs till lösningen, som när algoritmen är klar kommer att vara ett träd, men som i detta skede är en skog bestående av två än så länge separata träd.200px|vänster DF läggs till lösningen.200px|vänsterAB och BE har lägst kostnad. AB läggs till enligt alfabetisk ordning. BD kan därmed inte ingå i denna lösning, eftersom den bildar en cykel tillsammans med AB och AD, som redan ingår i lösningen.200px|vänster BE läggs till lösningen. Detta utesluter BC, DE och EF.200px|vänster Av de kanter som fortfarande kan ingå i lösningen (EG och FG) har EG lägst kostnad. (BC och EF har lägre kostnad, och BD har samma kostnad, men dessa skapar cykler.) EG läggs därför till lösningen. Det finns inga återstående kanter som vare sig ingår i lösningen eller bildar cykler i lösningen (och alla hörn ingår i trädet). Trädet är fullständigt.

Se även Prims algoritm Grafteori

Kategori:Grafalgoritmer