Breedte-eerst zoeken (BFS)
Doorzoekt een graaf laag voor laag. Een wachtrij bepaalt welke knoop de volgende is, dus de dichtstbijzijnde knopen komen altijd eerst aan de beurt.
- O(V + E)
- geheugen O(V)
- wachtrij
V en E: het aantal knopen (vertices) en kanten (edges). O(V + E) betekent dat elke knoop en elke kant een vast aantal keren aan de beurt komt.
Wachtrij: wie het eerst komt, gaat het eerst. BFS neemt altijd de knoop die het langst heeft gewacht.
Andere begrippen op deze pagina
- Knoop: een punt van de graaf, hier getekend als een cirkel met een letter.
- Kant: een lijn die twee knopen verbindt. Je kunt hem hier in beide richtingen volgen.
- Buren: de knopen die via een kant met een knoop verbonden zijn. Ze worden in alfabetische volgorde bekeken.
- in de wachtrij
- huidige
- afgerond
- kant van de zoekboom
- overgeslagen kant
Begin bij A. Druk op afspelen of doorloop de zoektocht stap voor stap.
Spatie: afspelen of pauzeren. Pijltjes links/rechts: stap. Home en End: springen.
Probeer dit: Kies de graaf met twee delen. De knopen die niet met de start verbonden zijn, worden nooit bereikt.
Hoe het werkt
BFS zet de startknoop in een wachtrij. Daarna haalt het steeds opnieuw de knoop vooraan uit de wachtrij en zet zijn nieuwe buren achteraan. Een wachtrij werkt in volgorde van aankomst. Zo zijn alle knopen op één kant afstand afgerond voordat een knoop op twee kanten afstand aan de beurt komt. Het getal naast een knoop is zijn afstand tot de start: het kleinste aantal kanten om hem te bereiken.
Wanneer het een goede keuze is
Gebruik BFS als je de kortste weg in stappen zoekt: de minste zetten in een puzzel, de minste hops in een netwerk, de mensen binnen twee connecties van jou. In een grote graaf kan de wachtrij lang worden, want die bevat een hele laag tegelijk.