Het algoritme van Kruskal

Sorteer de kanten, neem de kortste, sluit nooit een lus. Het algoritme van Kruskal is misschien wel het eenvoudigste gretige algoritme dat er is, en toch vindt het altijd de goedkoopste manier om elke knoop van een graaf te verbinden.

Een graaf waarin meerdere stukken van een boom tegelijk groeien, een overgeslagen kant die een cyclus zou sluiten rood gestreept, en daaronder de lijst met kanten die nog geprobeerd moeten worden
Een graaf waarin meerdere stukken van een boom tegelijk groeien, een overgeslagen kant die een cyclus zou sluiten rood gestreept, en daaronder de lijst met kanten die nog geprobeerd moeten worden

Het idee

Een minimale opspannende boom verbindt elke knoop van een gewogen graaf met de kleinst mogelijke totale kantlengte. Het algoritme van Kruskal laat niet één boom groeien vanaf een start. Het bekijkt de hele graaf tegelijk, begint met elke knoop als een eigen stuk en blijft stukken verbinden met de kortste beschikbare kant tot er nog maar één stuk over is.

Stap voor stap

Sorteer de kanten van kort naar lang. Probeer ze in die volgorde. Liggen de twee uiteinden van een kant in verschillende stukken, voeg hem dan toe aan de boom: de twee stukken worden één. Liggen beide uiteinden al in hetzelfde stuk, dan zou de kant een cyclus sluiten, dus sla hem over. Met n knopen is de boom klaar na n − 1 kanten, en de overige kanten hoeven nooit bekeken te worden.

Een voorbeeld

Neem de kanten A–B met lengte 1, B–C 2, A–C 3, C–D 4 en B–D 5. Kruskal voegt A–B toe, dan B–C, waarmee C bij het stuk A–B komt. Daarna komt A–C, maar A en C zitten al in één stuk, dus die kant zou de cyclus A–B–C sluiten en wordt overgeslagen. C–D sluit D aan, en nu vormen alle vier knopen één boom met drie kanten, met totale lengte 7. B–D, de langste kant, wordt niet eens geprobeerd.

Union-find

De enige lastige vraag die het algoritme van Kruskal stelt, is: zitten deze twee knopen al in hetzelfde stuk? Een union-find-structuur beantwoordt die. Elk stuk is een boompje van verwijzingen naar een vertegenwoordiger. Find volgt de verwijzingen naar de vertegenwoordiger; union hangt de ene vertegenwoordiger onder de andere. Padcompressie, die elke bezochte knoop direct naar de vertegenwoordiger laat wijzen, en unie op grootte houden de verwijzingen zo kort dat elke vraag bijna constante tijd kost.

Geschiedenis en snelheid

Joseph Kruskal publiceerde het algoritme in 1956, in een kort artikel in de Proceedings of the American Mathematical Society. Het sorteren van de kanten is het traagste deel, dus het werk groeit met E log E, voor E kanten. Zijn de kanten al gesorteerd, of zijn hun lengtes kleine gehele getallen, dan is het bijna lineair.

Probeer het zelf

Open de app en druk op Stap. De kanten die nog geprobeerd moeten worden, staan onder de graaf, kortste eerst. Elke kant die twee stukken verbindt, wordt groen; elke kant die een cyclus zou sluiten, wordt rood gestreept getekend. Zie hoe in verschillende delen van de graaf kleine stukken groeien en samensmelten, en hoe de laatste kanten vaak nooit geprobeerd worden.

Veelgestelde vragen

Waarom sorteert het algoritme van Kruskal de kanten?

Zodat elke kant die het toevoegt de kortste is die nog twee stukken verbindt. Die gretige keuze is altijd veilig dankzij de snede-eigenschap, en elke overgeslagen kant is de langste op de cyclus die hij zou sluiten, dus is nooit nodig.

Wat is een structuur voor disjuncte verzamelingen?

Een andere naam voor union-find: een structuur die een verzameling losse sets bijhoudt, hier de stukken van het groeiende bos, en snel kan zeggen bij welke set een element hoort en twee sets kan samenvoegen.

Werkt het algoritme van Kruskal op een niet-samenhangende graaf?

Ja. Het eindigt dan gewoon met één boom voor elk samenhangend stuk van de graaf, een minimaal opspannend bos, omdat geen kant stukken kan verbinden die niet verbonden zijn.

Wordt het algoritme van Kruskal ook voor andere dingen gebruikt?

Als je het vroeg stopt, voordat de laatste stukken samensmelten, deelt het de knopen in clusters in: dat is single-linkage-clustering. Laat je het lopen op een rooster met willekeurige kantlengtes, dan maakt het een doolhof.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Probeer het algoritme van Kruskal