Boomkanten
Totale lengte
Bekeken kanten

  • Huidig
  • In de boom
  • Zou een cyclus sluiten

Meer over het algoritme van Kruskal

Het algoritme van Kruskal

Het algoritme van Kruskal bouwt een minimale opspannende boom, de goedkoopste verzameling kanten die elke knoop verbindt, op de eenvoudigst denkbare manier: neem de kanten van kort naar lang en houd elke kant, tenzij hij een cyclus zou sluiten. Ga stap voor stap om losse stukken te zien groeien en samensmelten tot één boom, en om de overgeslagen kanten te zien. Druk op Afspelen om de boom te zien groeien, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen. Het getal op elke kant is de lengte ervan. Onder de graaf staan de kanten die nog geprobeerd moeten worden, van kort naar lang; een kant waarvan de uiteinden al verbonden zijn, zou een cyclus sluiten en is rood gestreept getekend. Nieuwe graaf maakt een andere graaf; kies hoeveel knopen en kanten die heeft. Als het bord geselecteerd is, gaan de pijltjestoetsen een stap verder of terug, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het einde.

Hoe het werkt

  1. Druk op Afspelen, of gebruik Stap en Terug om stap voor stap te gaan.
  2. Sleep de stappenschuif om ergens heen te springen. De kanten die nog geprobeerd moeten worden, staan onder de graaf, kortste eerst.
  3. Let op de rood gestreepte kanten: die zouden een cyclus sluiten. Nieuwe graaf maakt een andere graaf om te proberen.

Hoe het algoritme van Kruskal werkt

Sorteer alle kanten van kort naar lang. Begin met elke knoop als een eigen stuk. Probeer de kanten op volgorde: verbindt een kant twee verschillende stukken, dan gaat hij in de boom en worden de twee stukken één; liggen zijn twee uiteinden al in hetzelfde stuk, dan zou hij een cyclus sluiten, dus sla hem over. Stop als alles één stuk is. Dat gebeurt na één kant minder dan er knopen zijn, vaak lang voordat de laatste kant geprobeerd is.

Union-find

Bij elke kant moet het algoritme van Kruskal vragen of de twee uiteinden al verbonden zijn. Een union-find-structuur beantwoordt dat snel: elk stuk heeft één vertegenwoordiger, find volgt de verwijzingen naar die knoop, en union koppelt de ene vertegenwoordiger aan de andere. Met twee eenvoudige trucs, padcompressie en unie op grootte, kost elke vraag bijna constante tijd, dus het sorteren van de kanten is het traagste deel, met werk dat groeit met E log E.

Veelgestelde vragen

Wat is het algoritme van Kruskal?

Een gretig algoritme dat een minimale opspannende boom bouwt door alle kanten van kort naar lang te sorteren en elke kant toe te voegen die geen cyclus sluit met de kanten die al gekozen zijn.

Hoe ziet het algoritme van Kruskal een cyclus?

Een kant sluit precies een cyclus als zijn twee uiteinden al verbonden zijn door gekozen kanten. Een union-find-structuur houdt bij welke knopen verbonden zijn en beantwoordt die vraag bijna meteen.

Waarom werkt het algoritme van Kruskal?

Dankzij de cyclus-eigenschap: de langste kant op een cyclus is nooit nodig voor een minimale opspannende boom. Elke kant die Kruskal overslaat, is de langste op de cyclus die hij zou sluiten, want alle kanten ervoor waren korter of even lang.

Wanneer gebruik ik Kruskal in plaats van Prim?

Het algoritme van Kruskal is eenvoudig en snel op ijle grafen, en werkt direct op een gewone lijst van kanten. Het algoritme van Prim past bij dichte grafen en grafen die als burenlijsten zijn opgeslagen. Beide vinden een boom met dezelfde totale lengte.

Wordt mijn graaf ergens heen gestuurd?

Nee. De graaf wordt in je browser gemaakt en de boom wordt er gebouwd, en je laatste instellingen blijven in de lokale opslag van deze browser.

Klaar om het te proberen?

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

Ga naar Editor