====== 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.

[[it_encyklopedie:algoritmus|Zpět na Algoritmy]]