Prohledávání grafu do šířky

Jde o grafový algoritmus, který postupně prochází všechny vrcholy daného souvislého grafu. Algoritmus nejprve projde všechny následníky startovního vrcholu, poté následníky následníků a tak dál až projde celý souvislý graf. Při zpracovávání uzlu řadíme všechny jeho následníky do fronty (FIFO) a zpracováváme vždy první uzel z fronty.

Vstup: Vstupem algoritmu je libovolný orientovaný nebo neorientovaný souvislý graf.

Inicializace: Na začátku algoritmu uložíme do frontystartovací uzel (vrchol grafu, ve kterém zahajujeme prohledávání).

Popis: Vybereme vrchol, který je na začátku fronty a na konec fronty přidáme všechny jeho přímé následníky, do kterých vede z tohoto vrcholu hrana a u nichž ještě nebylo ukončeno prohledávání (které zatím neprošly frontou). Prohledávání tohoto vrcholu poté ukončíme. Opět vybereme vrchol na počátku fronty a celý postup opakujeme. Nemá-li některý z vrcholů žádné následníky, rovnou ukončíme jeho prohledávání a přejdeme k vrcholu na začátku fronty. Algoritmus končí, jakmile je fronta prázdná a nemáme dál co prohledávat.

Výstup: Výstupem algoritmu je pořadí uzlů v jakém byly ukládány do fronty (pořadí, v jakém bylo ukončeno jejich prohledávání).

Následující obrázek ilustruje, jak algoritmus prohledávání grafu do šířky prochází grafem: