Boomkanten
Totale lengte
Bekeken kanten

  • Huidig
  • In de boom
  • Naast de boom
  • Beste kant tot nu toe
  • Zou een cyclus sluiten

Meer over minimale opspannende bomen

Minimale opspannende boom

Je wilt elke stad met kabel verbinden, elk huis met waterleidingen of elke computer in een netwerk, met zo weinig mogelijk materiaal. Het antwoord is een minimale opspannende boom: de kanten die elke knoop verbinden met de kleinste totale lengte. Kies het algoritme van Kruskal of Prim en ga stap voor stap om de boom te zien groeien, telkens met de kortste kant die mag. 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. Kies het algoritme: Kruskal probeert de kanten van kort naar lang, Prim laat één boom groeien vanaf de start; klik op een knoop om die de start van Prim te maken. Het getal op elke kant is de lengte ervan. Onder de graaf staat de lijst met kanten die nog geprobeerd moeten worden, of de knopen die wachten om aan te sluiten, met de lengte van hun beste kant naar de boom. 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. Kies het algoritme van Kruskal of Prim. Klik bij Prim op een knoop om die de start te maken.
  2. Druk op Afspelen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen.
  3. Volg hoe de kanten in de boom komen en de totale lengte groeit. Nieuwe graaf maakt een andere graaf om te proberen.

Het algoritme van Kruskal

Sorteer alle kanten van kort naar lang en probeer ze in die volgorde. Verbindt een kant twee stukken die nog niet verbonden zijn, dan gaat hij in de boom. Zijn de twee uiteinden al via de boom verbonden, dan zou hij een cyclus sluiten en wordt hij overgeslagen. Stop als de boom één kant minder heeft dan er knopen zijn. Om snel te zien of twee knopen al verbonden zijn, houdt het algoritme van Kruskal de stukken bij in een union-find-structuur.

Het algoritme van Prim

Begin met een boom van één knoop. Elke knoop buiten de boom onthoudt zijn kortste kant naar de boom. Voeg steeds de knoop met de kortste kant toe, samen met die kant, en bekijk de kanten ervan: een daarvan kan een buur een kortere weg naar de boom geven. Het algoritme van Prim lijkt op het algoritme van Dijkstra, maar vergelijkt losse kanten, geen hele afstanden vanaf de start. Beide algoritmen eindigen altijd met dezelfde totale lengte.

Veelgestelde vragen

Wat is een minimale opspannende boom?

Voor een samenhangende graaf waarvan de kanten lengtes hebben, is een opspannende boom een verzameling kanten die alle knopen verbindt zonder cyclus; met n knopen heeft die altijd n − 1 kanten. Een minimale opspannende boom is een opspannende boom met een zo klein mogelijke totale lengte.

Wat is het verschil tussen het algoritme van Kruskal en dat van Prim?

Het algoritme van Kruskal bekijkt de kanten van de hele graaf van kort naar lang en voegt losse stukken samen tot één boom. Het algoritme van Prim laat één boom groeien vanaf een start en voegt steeds de kortste kant toe die eruit vertrekt. Beide zijn gretig en vinden een boom met dezelfde totale lengte; Kruskal past bij ijle grafen, Prim bij dichte.

Is de minimale opspannende boom uniek?

Als alle kantlengtes verschillen, ja. Zijn sommige lengtes gelijk, dan kunnen er meerdere bomen zijn met hetzelfde kleinste totaal, en kunnen de algoritmen verschillende kiezen, afhankelijk van hoe ze tussen gelijke kanten kiezen.

Is een minimale opspannende boom hetzelfde als kortste paden?

Nee. De minimale opspannende boom houdt de totale lengte van alle kanten klein, maar het pad tussen twee knopen in de boom kan veel langer zijn dan hun kortste pad. Gebruik voor kortste paden het algoritme van Dijkstra.

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