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.

Kruskals algoritm
MST kruskal en.gif
Girig algoritm, grafalgoritm Redigera
Uppkallad efterJoseph Kruskal Redigera
Utgiv­nings­da­tum1956 Redigera
Upp­täc­ka­re eller skapareJoseph Kruskal Redigera
Löserminimalt uppspännande träd Redigera

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.

PseudokodRedigera

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

ExempelRedigera

Bild Beskrivning
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.
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.
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.
DF läggs till lösningen.
AB 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.
BE läggs till lösningen. Detta utesluter BC, DE och EF.
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 ävenRedigera