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 rediger
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 rediger
- 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).