Bredde-først-søk

Bredde-først-søk (BFS) er en søkealgoritme for grafer som fra en node søker nivå for nivå nedover i en trestruktur.

Virkemåte
Algoritmen går systematisk gjennom grafen ved å undersøke om noden som kontrolleres har barn. Dersom dette er tilfellet, blir de lagt til i en kø (noden markeres i blått på illustrasjonen). Deretter hentes en og en node ut av køen og sammenlignes med det som søkes etter. Så lenge ikke riktig node er funnet, legges nodens eventuelle barn til i køen, og algoritmen henter ut neste objekt. På denne måten blir alle søskennodene (nodene på samme nivå) søkt gjennom før traverseringen fortsetter ned på neste nivå.

Algoritme
 Legg rotnoden til i køen
 Hent en node ut av køen og undersøk den
 Hvis noden stemmer overens med ønsket resultat, avslutt algoritmen og returner resultatet
 Hvis ikke, legg nodens barn til i køen
 Hvis køen er tom, er alle nodene i grafen undersøkt og søket må avsluttes uten resultat
 Gjenta fra steg 2

NB: Å bruke en stabel i stedet for en kø, gjør søkealgoritmen til et dybde-først-søk (DFS). 

Kategori:Søkealgoritmer