Kruskals algoritme

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.

Voorbeeld

	Dit is de gegeven graaf. De cijfers naast de bogen zijn de gewichten. Bij aanvang van het algoritme zijn er nog geen bogen gekozen. De eerste kandidaten zijn dus die bogen die het kleinste gewicht hebben.
	Bogen AD en CE met lengte 5 zijn de kortste (nog niet gekozen) bogen. We kiezen er willekeurig een uit, in dit geval AD.
	Nu is CE de kortste, nog niet gekozen boog. We kunnen die kiezen omdat ze met de reeds gekozen boog AD geen kring vormt.
	De volgende kandidaat is boog DF met lengte 6. Ze vormt geen kring met de reeds gekozen bogen en wordt dus gekozen.
	De volgende kandidaten zijn AB en BE die beide lengte 7 hebben. We kiezen willekeurig boog AB. Boog BD zou nu met bogen AB en AD een kring vormen. BD mag dus in het verdere verloop van het algoritme niet meer beschouwd worden. We kleuren die daarom rood.
	BE, met lengte 7, is nu de kortste nog niet gekozen boog die geen kring vormt met de reeds gekozen bogen. Bogen BC, DE en FE zouden nu wel een kring vormen en worden daarom ook rood gekleurd. Enkel bogen FG en EG zijn nu nog niet aan de beurt geweest.
	Als laatste wordt boog EG met lengte 9 gekozen. De laatst overblijvende boog FG wordt rood omdat ze een kring zou vormen met reeds gekozen bogen. Er blijven nu geen bogen meer over, en dus stopt het algoritme. De groene bogen vormen nu een minimale opspannende boom van de gegeven graaf.

Merk op dat de gekozen bogen tijdens het verloop van het algoritme niet altijd een boom vormen maar een "woud" van niet-verbonden bomen. Maar aan het einde zal er wel een boom overblijven. Wanneer er meerdere kandidaat-bogen met hetzelfde gewicht zijn, moet men er een kiezen en bij een andere keuze kan men een andere minimaal opspannende boom bekomen. Enkel wanneer alle bogen een verschillend gewicht hebben, is er een unieke minimaal opspannende boom.

Zie ook

Andere algoritmes voor dit probleem zijn Prims algoritme, het Reverse-Delete-algoritme en Borůvka's algoritme.

Bronnen, noten en/of referenties

1. Joseph B. Kruskal, Jr. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society 7 (1): 48-50. DOI: 10.1090/S0002-9939-1956-0078686-7.