BFS

O(V + E)

Prohledávání do šířky prochází graf po jednotlivých vrstvách. Začne ve výchozím uzlu, navštíví všechny jeho přímé sousedy, pak jejich sousedy a tak dál. Fronta (FIFO) drží uzly čekající na zpracování v pořadí příchodu — právě díky tomu jde průchod úroveň po úrovni a v neohodnoceném grafu najde nejkratší cestu.

Klik do prázdna = vrchol · klik na 2 vrcholy = hrana · táhni = posuňStart: A
Vstupní graf
Strom BFS
Stiskni ▶ a spusť
Fronta
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Vlož výchozí uzel do fronty a označ ho jako navštívený.
  2. Vyjmi uzel ze začátku fronty a zpracuj ho.
  3. Projdi jeho sousedy; každého nenavštíveného označ a přidej na konec fronty.
  4. Opakuj, dokud není fronta prázdná — pak jsou navštíveny všechny dosažitelné uzly.

Pseudokód

1BFS(graph, start):2  visited ← { start }3  queue ← [ start ]4  while queue is not empty:5    node ← queue.dequeue()         # take from the front6    process(node)7    for each neighbour of node:8      if neighbour not in visited:9        visited.add(neighbour)10        queue.enqueue(neighbour)    # add to the back