Boomkanten
Totale lengte
Bekeken kanten

  • Huidig
  • In de boom
  • Naast de boom
  • Beste kant tot nu toe

Meer over het algoritme van Prim

Het algoritme van Prim

Het algoritme van Prim bouwt een minimale opspannende boom, de goedkoopste verzameling kanten die elke knoop verbindt, door één boom te laten groeien vanaf een start. Bij elke stap voegt het de knoop toe die met de kortste kant vanaf de boom te bereiken is. Klik op een knoop om daar te beginnen en ga stap voor stap om de wachtende knopen, hun beste kanten en de groeiende boom 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. Klik op een knoop om die de start te maken: daar begint de boom te groeien. Het getal op elke kant is de lengte ervan. Onder de graaf staan de knopen die wachten om aan te sluiten, met de lengte van hun beste kant naar de boom, die gestreept is 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. Klik op een knoop om die de start te maken: daar begint de boom te groeien.
  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 de wachtende knopen onder de graaf, elk met zijn beste kant naar de boom. Nieuwe graaf maakt een andere graaf om te proberen.

Hoe het algoritme van Prim werkt

Begin met een boom van één knoop. Elke knoop buiten de boom onthoudt zijn kortste kant naar de boom, als hij die heeft. Neem steeds de knoop met de kortste kant, voeg hem met die kant toe aan de boom en bekijk zijn kanten: is er een korter dan de beste kant van een buur tot nu toe, dan wordt die de nieuwe beste kant van die buur. Als elke knoop is aangesloten, heeft de boom één kant minder dan er knopen zijn, en is zijn totale lengte zo klein mogelijk.

Prim en Dijkstra

Het algoritme van Prim en het algoritme van Dijkstra lijken bijna hetzelfde: beide laten een gebied groeien vanaf een start en houden de wachtende knopen bij in een prioriteitswachtrij. Het verschil is het getal in de wachtrij. Dijkstra bewaart de hele afstand van elke knoop tot de start; Prim alleen de lengte van zijn ene beste kant naar de boom. Dijkstra bouwt dus een boom van kortste paden, en Prim een boom met de kleinste totale lengte, en die twee bomen verschillen vaak.

Veelgestelde vragen

Wat is het algoritme van Prim?

Een gretig algoritme dat een minimale opspannende boom van een gewogen graaf bouwt door één boom te laten groeien vanaf een startknoop, en steeds de kortste kant toevoegt die de boom met een knoop daarbuiten verbindt.

Maakt de startknoop uit?

Alleen voor de volgorde: vanaf elke start eindigt het algoritme van Prim met een opspannende boom met dezelfde kleinste totale lengte. Als sommige kanten even lang zijn, kan de boom zelf verschillen.

Wie heeft het algoritme van Prim bedacht?

Vojtěch Jarník beschreef het als eerste, in 1930. Robert Prim ontdekte het opnieuw in 1957 en Edsger Dijkstra in 1959, dus het heet ook het algoritme van Jarník of het algoritme van Prim–Jarník.

Hoe snel is het algoritme van Prim?

Met een binaire heap groeit het werk met E log V, voor V knopen en E kanten. Met een eenvoudige array in plaats van een heap kost het ongeveer V² stappen, wat beter is voor dichte grafen, waarin bijna elk paar knopen verbonden is.

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