Loading AI tools
Van Wikipedia, de vrije encyclopedie
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.
Het algoritme heeft een tijdscomplexiteit van O(bd), waarbij b de vertakkingsfactor van de graaf is en d de diepte van de graaf. Het algoritme heeft ook een ruimtecomplexiteit van O(bd). 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).
BFS kan geïmplementeerd worden met behulp van een FIFO queue. In pseudocode werkt het algoritme als volgt:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.