Page 166 - Demo
P. 166

TI Python BootCamp Python VERDIEPING 5 OOP
3. Prim-algoritme
Het Prim-algoritme is een algoritme om de minimale opspannende boom van een graaf te bepalen. Even wat grafen-terminologie.
Hieronder wat bomen die samen een bos vormen:
    Een acyclische graaf een graaf is zonder cykel (= pad met lengte groter dan nul van een punt naar zichzelf); ook wel
een bos genoemd. Een boom is samenhangende acyclische graaf.
    Een opspannende boom is een deelgraaf die alle punten van de graaf bevat. Indien we aan de punten een gewicht
 toekennen, bv de kost of de afstand van een wandeling tussen twee punten, spreken we een gewogen boom.
 Het Prim-algoritme bepaalt de minimale (gewogen) opspannende boom, m.a.w. de boom met minimale gewicht, kost
 of afstand. We coderen een Prim-algoritme met als gewicht de Euclidische afstand tussen de punten.
 Voor een graaf tekenen we de Euclidisch minimale opspannende boom (EMST – Euclidean minimum spanning tree).
 Een EMST verbindt een verzameling punten met lijnen zodat de totale lengte van de lijnen minimaal is en zodat ieder
punt kan bereikt worden vanuit ieder ander punt door deze lijnen te volgen.
     We bouwen het algoritme als volgt op voor een verzameling van punten:
 1. 2.
3.
Zoek voor dit punt p het punt q uit de lijst van niet verbonden punten waarvoor geldt dat de afstand minimaal is.
a. b. c.
Herhaal stap 2 voor alle verbonden punten tot de er geen niet verbonden punten meer zijn
Start een boom met een willekeurig punt p (verbonden) en een lijst met punten die nog niet toegevoegd zijn aan
 de boom (niet verbonden). Bij de start zijn dit alle punten uitgezonderd het willekeurig gekozen punt p.
  Verbind de punten p en q,
 verwijder q van de lijst van niet verbonden punten en
 voeg q toe aan de verbonden punten van de boom.
     © 2020 T3 Nederland – T3 Vlaanderen 4 www.t3nederland.nl – www.t3vlaanderen.be










































































   164   165   166   167   168