Prehľadávanie do šírky (BFS)
Prechádza graf vrstvu po vrstve. O ďalšom vrchole rozhoduje front, takže najbližšie vrcholy sú vždy navštívené ako prvé.
- čas O(V + E)
- pamäť O(V)
- používa front
Čo to znamená?
- Vrchol: bod grafu, tu nakreslený ako krúžok s písmenom.
- Hrana: čiara, ktorá spája dva vrcholy. Tu sa po nej dá ísť oboma smermi.
- Susedia: vrcholy spojené s daným vrcholom hranou. Prezerajú sa v abecednom poradí.
- Front: kto prv príde, ten prv odíde. BFS vždy berie vrchol, ktorý čaká najdlhšie.
- Zásobník: kto príde posledný, odíde prvý. DFS vždy pokračuje z vrcholu, ku ktorému sa dostal naposledy.
- V a E: počet vrcholov a hrán. O(V + E) znamená, že každý vrchol a každá hrana sa spracuje iba pevne daný počet ráz.
- vo fronte
- aktuálny
- hotový
- hrana stromu prehľadávania
- preskočená hrana
Začnite vo vrchole A. Stlačte Prehrať alebo prechádzajte prehľadávanie krok po kroku.
Medzerník: prehrať alebo pozastaviť. Šípky vľavo/vpravo: krok. Home a End: preskočiť.
Skúste: Zvoľte graf s dvoma časťami. K vrcholom, ktoré nie sú spojené so štartom, sa prehľadávanie nikdy nedostane.
Ako to funguje
BFS vloží počiatočný vrchol do frontu. Potom znova a znova vezme vrchol zo začiatku frontu a jeho nových susedov pridá na koniec. Front obsluhuje v poradí príchodu, takže každý vrchol vzdialený o jednu hranu je hotový skôr než ktorýkoľvek vrchol vzdialený o dve. Číslo pri vrchole je jeho vzdialenosť od štartu: najmenší počet hrán, po ktorých sa k nemu dá dôjsť.
Kedy sa hodí
BFS použite, keď hľadáte najkratšiu cestu v krokoch: najmenej ťahov v hlavolame, najmenej skokov v sieti, svojich priateľov a priateľov priateľov. Na veľkom grafe môže front poriadne narásť, lebo drží celú vrstvu naraz.