Breadth-first search

Breadth-first search (BFS) is een zoekalgoritme op een graaf dat begint bij de wortel (beginknoop) van de graaf en dat voor elk van de kinderen kijkt of het de oplossing is en vervolgens voor elk van die kinderen dit proces uitvoert totdat de gewenste oplossing gevonden is. BFS is een vorm van ongeïnformeerd zoeken, aangezien het geen informatie over het zoekprobleem gebruikt tijdens het zoeken.

Kenmerken

Het algoritme heeft een tijdscomplexiteit van O(b^d), waarbij b de vertakkingsfactor van de graaf is en d de diepte van de graaf. Het algoritme heeft ook een ruimtecomplexiteit van O(b^d). Deze zoekmethode is compleet: als er een oplossing bestaat, zal een breadth-first search deze vinden maar als de graaf een oneindig aantal knopen bevat en geen oplossing, dan zal het algoritme niet termineren.

Als elke kant in de graaf dezelfde hoeveelheid kosten met zich meebrengt, dan is het algoritme optimaal: het zal dan een pad kunnen vinden van de wortel naar de oplossing met optimale kosten. Op een gewogen graaf kan het zijn dat BFS geen optimale oplossing teruggeeft, aangezien het kortste pad dan niet langer een optimale oplossing hoeft te betekenen (de kanten kunnen hoge kosten hebben terwijl een nog niet bekeken knoop een betere oplossing kan zijn).

Werking

BFS kan geïmplementeerd worden met behulp van een FIFO queue. In pseudocode werkt het algoritme als volgt:

Voeg de wortel van de graaf toe aan de queue
Als er een knoop in de queue zit, neem deze uit de queue en bekijk de knoop:
- Als dit een oplossing is: stop het zoeken en geef de oplossing
- Als dit geen oplossing is: voeg alle kinderen van deze knoop toe aan het einde van de FIFO queue
Als de queue leeg is: alle knopen zijn bekeken dus stop het zoeken en geef aan dat er geen oplossing is
Ga door naar stap 2

Zie ook

Depth-first search

Zie de categorie Breadth-first search van Wikimedia Commons voor mediabestanden over dit onderwerp.