Terug naar begrippenlijst
Breadth-First Search (BFS)
Breadth-First Search (BFS) is een algoritme dat wordt gebruikt om boom- of graafstructuren systematisch te doorzoeken. Het werkt laag voor laag: je begint bij een startpunt en verkent eerst alle directe buren, daarna de buren van de buren, enzovoorts. Net zo lang tot je het doel bereikt of alles hebt doorlopen. Stel je voor dat je in een doolhof staat. In plaats van willekeurig gangen in te rennen, besluit je eerst alle mogelijke gangen te checken vanaf je startpunt, daarna alle gangen die daaraan vast zitten, enzovoort. Dat is precies hoe BFS werkt: netjes, gestructureerd en stap voor stap.
Inhoudsopgave
Laag voor laag is het devies
In tegenstelling tot Depth-First Search (DFS), dat de diepte in duikt, blijft BFS juist breed. Het algoritme maakt gebruik van een wachtrij om bij te houden welke punten nog verkend moeten worden. Zo weet je altijd wat de volgende stap is en voorkom je dat je verdwaalt in een wirwar van paden.
BFS is bijzonder nuttig wanneer je:
- De kortste route wilt vinden in een ongewogen graaf (bijvoorbeeld in routing of navigatie)
- Iets zoekt waarvan je zeker weet dat het zich relatief dicht bij het startpunt bevindt
- Alle paden op volgorde van afstand van de bron wilt verkennen
Praktische toepassingen van BFS
Breadth-First Search is niet alleen een favoriet onder programmeurs en informaticastudenten die algoritmes leren, het wordt ook volop ingezet in échte toepassingen. Een paar herkenbare voorbeelden:
- AI en games: Het vinden van de snelste route voor een personage
- Netwerktools: Het verkennen van netwerken, zoals in social media of routers
- Zoekmachines: Het doorlopen van websitelinks op logische volgorde
De code erachter? Best overzichtelijk
Een typische BFS-implementatie gebruikt een wachtrij en een lijst om bij te houden welke knopen al bezocht zijn. Zo voorkom je loops en dubbele stappen. De structuur is overzichtelijk en leent zich goed voor uitbreidingen, zoals het tellen van stappen of het onthouden van het pad.
Veelgestelde vragen
BFS verkent eerst de breedte (alle buren op hetzelfde niveau), terwijl DFS de diepte in duikt (verder gaat langs één pad tot het niet meer kan).
Omdat het stap voor stap alle mogelijke routes van dichtbij naar ver weg afgaat. Zodra BFS het doel bereikt, weet je zeker dat het dat via de kortst mogelijke weg heeft gedaan. Simpelweg omdat langere routes nog niet aan de beurt waren.
Denk aan routeplanning (bijvoorbeeld in Google Maps), vriendensuggesties op social media of AI-navigatie in games.
Niet altijd. Als je veel geheugen hebt en de kortste route wilt, is het top. Maar bij hele diepe grafen of beperkte resources kan DFS efficiënter zijn.
Thijn de Haas Lead developer
