Kruskals algoritm

Kruskals algoritm

Girig algoritm, grafalgoritm

Uppkallad efter	Joseph Kruskal
Utgiv­nings­da­tum	1956
Upp­täc­ka­re eller upp­fin­na­re	Joseph Kruskal
Löser	minimalt uppspännande träd
Tids­komp­lex­i­tet i värsta fall	${\displaystyle O(E\log V)}$

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	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 även

• Prims algoritm
• Grafteori