Hledání cesty BFS

O(V + E)

Na neohodnocené mřížce najde prohledávání do šířky nejkratší cestu mezi dvěma buňkami. Rozšiřuje se ze startu ve vlnách: nejprve všechny buňky o krok daleko, pak o dva a tak dál, s využitím fronty. Protože každý pohyb stojí stejně, jakmile vlna poprvé zasáhne cíl, dorazila k němu nejkratší cestou, kterou získáš sledováním ukazatelů na rodiče zpět. BFS je tu úplné a optimální, ale prozkoumává slepě do všech směrů — netuší, kde cíl je — takže může navštívit mnohem víc buněk než řízené hledání. Běží v O(V + E).

Klikni na buňku pro přepnutí zdi
Mřížka
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Vlož startovní buňku do fronty a označ ji jako viděnou.
  2. Vyjmi nejbližší buňku a rozviň ji.
  3. Přidej každého volného neviděného souseda do fronty a zapamatuj, odkud přišel.
  4. Když je cíl vyjmut z fronty, sleduj ukazatele na rodiče zpět a vytrasuj nejkratší cestu.

Pseudokód

1bfsPath(grid, start, goal):          # O(V + E)2  queue ← [start]; seen ← {start}3  while queue not empty:4    cell ← queue.dequeue()           # nearest first5    if cell = goal: stop6    for nbr in free neighbours(cell):7      if nbr not seen:8        prev[nbr] ← cell; seen.add(nbr)9        queue.enqueue(nbr)10  walk prev from goal back to start  # shortest path