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.

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.

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

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.

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