BFS (Breadth-First Search)

Prohledávání do šířky je jeden ze základních algoritmů teorie grafů. Jeho hlavní charakteristikou je, že prozkoumává všechny uzly v aktuální vzdálenosti od startu předtím, než se přesune k uzlům, které jsou o krok dále.

1. Jak BFS funguje?

Algoritmus využívá datovou strukturu fronta (queue) pracující na principu FIFO (First-In, First-Out).

1. Vložte startovní uzel do fronty a označte jej jako navštívený.
2. Dokud není fronta prázdná:
* Vyjměte uzel z čela fronty.
* Prozkoumejte všechny jeho sousedy, které jste ještě nenavštívili.
* Každého takového souseda označte jako navštíveného a vložte jej na konec fronty.

2. Klíčové vlastnosti a výhody

Nejkratší cesta: V grafech, kde mají všechny hrany stejnou váhu (cenu), BFS vždy najde nejkratší cestu (minimální počet hran) mezi startem a cílem.

Složitost: Časová složitost je $O(V + E)$, kde $V$ je počet vrcholů a $E$ počet hran.

Paměťová náročnost: BFS bývá náročnější na paměť než DFS, protože musí v jeden okamžik uchovávat v paměti celou „frontu“ uzlů na dané úrovni.

3. Praktické využití

BFS je základem pro mnoho moderních technologií:

Sociální sítě: Hledání „přátel přátel“ nebo určení stupně odloučení mezi dvěma lidmi (např. LinkedIn „2nd degree connection“).

GPS navigace: Hledání nejkratší cesty v mapě (zjednodušená verze složitějších algoritmů jako Dijkstra).

P2P sítě: Hledání nejbližších sousedních uzlů v síti (např. BitTorrent).

Web crawlery: Indexování stránek vyhledávači tak, že se nejdříve projdou všechny odkazy na hlavní stránce.

4. Srovnání: BFS vs. DFS

Vlastnost	BFS (Do šířky)	DFS (Do hloubky)
Princip	Šíření ve vlnách.	Jde co nejdále v jedné větvi.
Datová struktura	Fronta (Queue).	Zásobník (Stack) / Rekurze.
Hledání cíle	Vhodné, pokud je cíl blízko startu.	Vhodné, pokud je cíl hluboko v grafu.
Nalezení nejkratší cesty	Ano (u neohodnocených grafů).	Ne.
Analogie: Představte si, že hledáte klíče v domě. BFS znamená, že nejdříve prohledáte celou podlahu v předsíni, pak všechny plochy v předsíni, a teprve pak jdete do další místnosti. DFS znamená, že vběhnete do kuchyně, otevřete jednu skříňku, v ní krabičku, v ní obálku… a až když tam klíče nejsou, vracíte se zpět.

Zpět na Algoritmy