Breedte-eerst zoeken (BFS)

Gooi een steen in een vijver en de rimpelingen verspreiden zich gelijkmatig in ringen. Breedte-eerst zoeken verkent een graaf op dezelfde manier: eerst alles op één stap van de start, dan alles op twee stappen, enzovoort. Door die eenvoudige volgorde vindt het kortste paden.

Een graaf met knopen met letters, in ringen gekleurd naar hun afstand tot de startknoop, met daaronder een wachtrij van knopen
Een graaf met knopen met letters, in ringen gekleurd naar hun afstand tot de startknoop, met daaronder een wachtrij van knopen

Het idee

Een graaf is een verzameling knopen die verbonden zijn door kanten: plaatsen en wegen, mensen en vriendschappen, vakjes van een doolhof en de openingen ertussen. Breedte-eerst zoeken beantwoordt de vraag: wat kan ik vanaf hier bereiken, en in hoe weinig stappen? Het houdt een wachtrij bij van knopen die nog bezocht moeten worden. Door knopen vooraan te nemen en nieuwe achteraan toe te voegen, worden de knopen behandeld in de volgorde waarin ze ontdekt zijn.

Stap voor stap

Zet de start in de wachtrij op afstand 0. Neem de knoop vooraan. Voor elke buur die nog niet gezien is: noteer als afstand één meer dan die van de huidige knoop, onthoud de huidige knoop als de weg waarlangs hij bereikt is, en zet hem achteraan in de wachtrij. Sla buren over die al gezien zijn. Herhaal tot de wachtrij leeg is of het doel bereikt is.

Een voorbeeld

Neem een graaf met de kanten A–B, A–C, B–D, C–D, C–E en D–F, en begin bij A. Als A uit de wachtrij komt, worden B en C gevonden op afstand 1. B levert D op afstand 2. C ziet dat D al gezien is, en vindt E op afstand 2. D levert F op afstand 3. E en F vinden niets nieuws, en de wachtrij is leeg. Wie de onthouden knopen terugvolgt vanaf F, krijgt F ← D ← B ← A, dus een kortste pad van A naar F is A → B → D → F, drie kanten lang.

Waarom de afstanden kloppen

Elke knoop op afstand 1 komt in de wachtrij vóór elke knoop op afstand 2, elke knoop op afstand 2 vóór elke knoop op afstand 3, enzovoort, want de buren van een knoop komen pas in de wachtrij als die knoop er zelf uit gaat. Het eerste pad dat een knoop bereikt, heeft dus de minste kanten, en BFS hoeft nooit een afstand te verbeteren. Elke knoop wordt één keer genomen en elke kant vanaf beide uiteinden bekeken, dus het werk groeit met het aantal knopen plus het aantal kanten.

Geschiedenis en toepassingen

Konrad Zuse beschreef breedte-eerst zoeken in 1945, in werk aan zijn taal Plankalkül dat pas in 1972 verscheen. Edward F. Moore vond het in 1959 opnieuw uit om de kortste weg uit een doolhof te vinden, en C. Y. Lee gebruikte het in 1961 om draden op printplaten te leggen. Nu vindt het de minste zetten in puzzels, de graden van scheiding in sociale netwerken, de pagina's die een webcrawler het eerst bereikt en het dichtstbijzijnde vrije vakje in games. Als kanten een lengte hebben, is het algoritme van Dijkstra de veralgemening ervan.

Konrad Zuse (midden, met bril) en Heinz Billing (links) op de beurs SYSTEMS ’91 in München. Zuse beschreef breedte-eerst zoeken in 1945, in werk aan zijn taal Plankalkül dat pas in 1972 werd gepubliceerd.
Konrad Zuse (midden, met bril) en Heinz Billing (links) op de beurs SYSTEMS ’91 in München. Zuse beschreef breedte-eerst zoeken in 1945, in werk aan zijn taal Plankalkül dat pas in 1972 werd gepubliceerd.

Probeer het zelf

Open de app en druk op Stap. De knoop die bezocht wordt, is gemarkeerd, knopen die in de wachtrij wachten zijn blauw en bezochte knopen zijn groen, elk met zijn afstand. De wachtrij staat onder de graaf, de voorkant eerst. Zet de klik op Doel en kies een knoop om daar te stoppen en het kortste pad te zien, of maak een nieuwe graaf met meer knopen en kanten.

Veelgestelde vragen

Wat is de tijdcomplexiteit van BFS?

O(V + E) voor V knopen (vertices) en E kanten (edges): elke knoop gaat één keer de wachtrij in en uit, en elke kant wordt vanaf beide uiteinden bekeken. Het heeft O(V) extra geheugen nodig voor de wachtrij en de afstanden.

Waarom gebruikt BFS een wachtrij?

Omdat eerst erin, eerst eruit de knopen in de volgorde houdt waarin ze ontdekt zijn, en dat is de volgorde van hun afstand. Met een stapel zou het zoeken eerst de diepte in duiken: dat is diepte-eerst zoeken.

Kan BFS kortste paden vinden in gewogen grafen?

In het algemeen niet: het telt kanten, niet hun lengtes. Gebruik voor gewogen grafen zonder negatieve kanten het algoritme van Dijkstra. Is elk gewicht 0 of 1, dan werkt een variant die 0-1 BFS heet.

Waar wordt BFS gebruikt?

Om puzzels en doolhoven in zo weinig mogelijk zetten op te lossen, vrienden van vrienden te vinden in sociale netwerken, het web laag voor laag te doorzoeken, berichten door netwerken te verspreiden, en als bouwsteen van andere algoritmen, zoals het vinden van maximale stromen.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Probeer breedte-eerst zoeken