Breadth-first search, of BFS, is een methode om verbonden data laag voor laag te doorzoeken. Vanaf een startpunt kijkt het naar alles wat er direct mee verbonden is, dan naar alles wat met díe punten verbonden is, enzovoort. Het verkent elke ring van buren volledig voordat het naar de volgende stapt, en dat maakt het zo goed in het vinden van het kortste pad tussen twee punten.
Stel je voor dat je een steen in een vijver gooit. De rimpeling raakt eerst alles op één stap afstand, dan de volgende ring, dan de volgende, in mooi gelijkmatige golven. BFS verspreidt zich op dezelfde manier door een netwerk. Die ordelijke uitbreiding is waarom het achter dingen als ‘mensen die je misschien kent’ en routebepaling zit. Het is de natuurlijke tegenhanger van depth-first search, dat juist eerst één pad afduikt voordat het andere verkent, en het kan elke binaire boom laag voor laag doorlopen.
Onder de motorkap gebruikt BFS een queue, een simpele eerst-in-eerst-uit-rij, om bij te houden welke buren het hierna moet bezoeken. Die nette boekhouding garandeert dat het in gelijkmatige ringen verkent en de kortste route vindt.
Je komt BFS vaker tegen dan je denkt. De ‘six degrees of separation’ tussen twee mensen op een sociaal netwerk is een BFS-probleem: in hoe weinig stappen zijn ze verbonden? Een navigatie-app die uitrekent met hoe weinig overstappen je door een metrokaart komt, leunt op hetzelfde idee. Net als een tool die alle bestanden vindt die worden geraakt als één gedeelde component verandert. Het enige om op te letten is geheugen. Omdat BFS een hele ring knooppunten tegelijk onthoudt, kan een heel breed netwerk die queue snel vullen, en dan grijpt een developer juist naar een depth-first-aanpak. De keuze ertussen gaat minder over slimheid en meer over het matchen van de methode aan de vorm van de data en het antwoord dat je echt nodig hebt.
Bij TopDevs passen we algoritmes als BFS toe als het probleem van een klant eigenlijk over verbindingen en kortste paden gaat, zodat de functie binnen milliseconden de juiste route teruggeeft.
