title: Algoritme van Prim
text: Het algoritme van Prim is een algoritme om de minimaal opspannende boom van een graaf te vinden.
  
  Het algoritme werd in 1930 ontdekt door de wiskundige Vojtěch Jarník en in 1957 onafhankelijk herontdekt door de informaticus Robert C. Prim. In 1959 werd het ook door Dijkstra ontdekt. Het algoritme wordt ook weleens het DJP-algoritme of algoritme van Jarnik genoemd.
  
  Algoritme
  Gegeven een samenhangende gewogen graaf  met een verzameling knopen .
  De volgende procedure is een algoritme dat een minimale opspannende boom T construeert.
  
  Start: Initialiseer  met  zodanig dat  de tak van minimale lengte vanuit  is. (Merk op dat  de notatie voor ongeordende paren is: de bogen zijn ongericht.)
  Stop: Stop zodra  precies  bogen heeft.
  Boog toevoegen:
  
  Van alle bogen die een knoop van  verbinden met een knoop die niet tot  behoort, voeg de boog met het kleinste gewicht toe (indien meerdere met het kleinste gewicht, een ervan kiezen).
  
  Deze boog bestaat aangezien het een samenhangende graaf is en  nog niet alle knopen bevat.  zal door deze stap geen kringen bevatten aangezien de toegevoegde knoop nog niet in  zat. Ga terug naar de stap Stop.
  
  Voorbeeld
  
  Zie ook 
   Kruskals algoritme
   Grafentheorie
  
  Discrete wiskunde
  Algoritme