Kruskals algoritme
Uit Wikipedia, de vrije encyclopedia
Kruskals algoritme is een algoritme uit de grafentheorie om de minimaal opspannende boom te vinden voor gewogen grafen. Hierbij zoeken we een deelverzameling van bogen die een boom vormen die alle knopen bevat, waarbij daarenboven het totale gewicht minimaal is. Als de graaf niet volledig verbonden is dan zoekt het een minimaal opspannend woud (een minimale overspannende boom voor elke onverbonden deelgraaf). Kruskals algoritme, beschreven in 1956[1] is een voorbeeld van een gulzig algoritme.
Het algoritme kan als volgt geformuleerd worden (G is de gegeven graaf):
"Voer de volgende stap zo vaak uit als mogelijk: Kies uit de bogen van G die nog niet werden gekozen, de kortste boog die geen kring vormt met de bogen die reeds werden gekozen."
Met "kortste boog" bedoelt men de boog met het kleinste gewicht. Als er geen kandidaten meer overblijven vormen de geselecteerde bogen de minimaal opspannende boom.