Druhou implementací efektivního průchodu grafu je průchod do šířky (BFS, neboli Bread First Search). Jeho výhodou o proti DFS je, že kromě samotného řešení nalezne i nejkratší cestu, která k řešení vede.

Prohledávání začneme ve vrcholu $s$ a projdeme celou komponentu souvislosti, do které $s$ patří. Délku cesty měříme počtem hran na cestě. Proměnná ${\tt H}[v]$ bude obsahovat délku nejkratší cesty z $s$ do $v$. Na začátku bude obsahovat hodnotu $-1$. V momentě, kdy se při průchodu grafu dostaneme do vrcholu $v$, nastavíme proměnnou ${\tt H}[v]$ na správnou hodnotu, což bude číslo větší nebo rovno nule. Proto podle hodnoty ${\tt H}[v]$ poznáme, jestli jsme už vrcholem $v$ někdy prošli a nebo ještě ne.

BFS($s$):
	 $\forall v\in V\,:$   H[$v$]:=$-1$
	 H[$s$]:=$0$ a přidej $s$ do fronty
	 while fronta neprázdná do
		 odeber vrchol $v$ z fronty
		 forall sousedy $w$ vrcholu $v$ do
			 if H[$w$]=$-1$  then
				 přidej $w$ do fronty
				 H[$w$]:=H[$v$]$+1$
Pozorování: Nejprve zpracujeme všechny vrcholy se stejným číslem ${{\tt H}[v]}$ a pak teprve začneme zpracovávat vrcholy s číslem o jedna větším. V průběhu algoritmu jsou ve frontě jen vrcholy, které mají ${{\tt H}[v]}$ rovno $d$ nebo $d+1$, pro nějaké $d$.

Díky tomu, že zpracování vrcholů probíhá po vlnách podle čísla ${\tt H}[v]$, se algoritmu říká algoritmus vlny.

Pozorování: ${\tt H}[v]$ obsahuje délku nejkratší cesty z $s$ do $v$.

Pozorování dokážeme indukcí podle hodnoty ${\tt H}[v]$. Vrchol $s$ má ${\tt H}[s]=0$ a nejkratší cesta z $s$ do $s$ má rovněž délku nula. Předpokládejme, že pro všechny vrcholy s hodnotou ${\tt H}[v]\le k$ je ${\tt H}[v]$ délka nejkratší cesty z $s$ do $v$. Potřebujeme ukázat indukční krok a to je, že každý vrchol $v$ s ${\tt H}[v]= k+1$ leží ve vzdálenosti $k+1$ od $s$. Pokud ne, tak existuje kratší cesta z $s$ do $v$ a nechť $wv$ je poslední hrana na této cestě. ${\tt H}[w] < k$. Potom se ale měl algoritmus při zpracovávání vrcholu $w$ podívat na hranu $wv$ a nastavit ${\tt H}[v]$ na ${\tt H}[w]+1$. Hodnota ${\tt H}[w]+1 < k+1$, což je spor. [medskip] Podobně jako v DFS tvoří stromové hrany DFS strom, tak i hrany, po kterých při BFS projdeme do nenavštíveného vrcholu, tvoří BFS strom (strom průchodu do šířky).

Jednotlivé “vlny” nazveme vrstvy průchodu do šířky. V $i$-té vrstvě jsou obsaženy právě vrcholy ve vzdálenosti $i$ od počátečního vrcholu $s$.


Příklad: Na kolik nejméně skoků doskáčeme šachovým koněm z A1 na A2? Úlohu vyřešíme pomocí průchodu do šířky (algoritmu vlny). Řešit ji můžeme přímo na papíře tak, že budeme do prázdných políček psát na kolik skoků se do nich dostaneme. Začneme na A1, kam napíšeme nulu. Do políček, kam doskočíme z A1 napíšeme jedničky. Ve druhé vlně napíšeme dvojku do všech políček, kam doskočíme z políček s jedničkou, atd. (do popsaných políček už nic nepíšeme). Skončíme ve chvíli, kdy se dostaneme do A2. Číslo napsané na políčku A2 udává nejmenší možný počet skoků.