Prohledávání do šířky (BFS)

Prochází graf vrstvu po vrstvě. O dalším vrcholu rozhoduje fronta, takže nejbližší vrcholy jsou navštíveny vždy jako první.

čas O(V + E)
paměť O(V)
používá frontu

Co to znamená?

Vrchol: bod grafu, tady nakreslený jako kroužek s písmenem.
Hrana: čára, která spojuje dva vrcholy. Tady se po ní dá jít oběma směry.
Sousedé: vrcholy spojené s daným vrcholem hranou. Prohlížejí se v abecedním pořadí.
Fronta: kdo dřív přijde, ten dřív odejde. BFS vždy bere vrchol, který čeká nejdéle.
Zásobník: kdo přijde poslední, odejde první. DFS vždy pokračuje z vrcholu, do kterého se dostal naposledy.
V a E: počet vrcholů a hran. O(V + E) znamená, že každý vrchol a každá hrana se zpracuje jen pevně daný počet krát.

0 / 60 kroků

ve frontě
aktuální
hotový
hrana stromu prohledávání
přeskočená hrana

Rychlost 8 kroků/s

Mezerník: přehrát nebo pozastavit. Šipky vlevo/vpravo: krok. Home a End: přeskočit.

Zkuste: Zvolte graf se dvěma částmi. K vrcholům, které nejsou spojené se startem, se prohledávání nikdy nedostane.

Jak to funguje

BFS vloží počáteční vrchol do fronty. Pak znovu a znovu vezme vrchol ze začátku fronty a jeho nové sousedy přidá na konec. Fronta obsluhuje v pořadí příchodu, takže každý vrchol vzdálený o jednu hranu je hotový dřív než kterýkoli vrchol vzdálený o dvě. Číslo u vrcholu je jeho vzdálenost od startu: nejmenší počet hran, po kterých se k němu dá dojít.

Kdy se hodí

BFS použijte, když hledáte nejkratší cestu v krocích: nejméně tahů v hlavolamu, nejméně skoků v síti, své přátele a přátele přátel. Na velkém grafu může fronta hodně narůst, protože drží celou vrstvu najednou.