Po przejrzeniu wszystkich sąsiadów danego węzła kolor węzła bieżącego zmieniany jest na czarny (wszyscy jego sąsiedzi zostali odwiedzeni) i operacja powtarza się dla następnego węzła znajdującego się w kolejce, bądź też (jeżeli kolejka jest pusta) algorytm kończy swoje działanie.
Właściwości Złożoność pamięciowa Złożoność pamięciowa algorytmu uzależniona jest od tego w jaki sposób reprezentowany jest graf wejściowy. W przypadku listy sąsiedztwa dla każdego wierzchołka przechowywana jest lista wierzchołków osiągalnych bezpośrednio z niego. W tym wypadku złożoność pamięciowa wynosi O(|V| + |E|) (zob. Asymptotyczne tempo wzrostu), gdzie |V| to liczba węzłów, a |E| to liczba krawędzi w grafie, odpowiadająca sumie wierzchołków znajdujących się na listach sąsiedztwa.
W przypadku macierzy sąsiedztwa wymagane jest przechowywanie macierzy o wymiarach |V|x|V|, czyli potrzebne jest O(|V|2) pamięci.
Złożoność czasowa Ponieważ w najgorszym przypadku przeszukiwanie wszerz musi przebyć wszystkie krawędzie prowadzące do wszystkich węzłów, złożoność czasowa przeszukiwania wszerz wynosi O(|V| + |E|), gdzie |V| to liczba węzłów, a |E| to liczba krawędzi w grafie.
Kompletność Przeszukiwanie wszerz jest kompletne, to znaczy, że gdy istnieje rozwiązanie, przeszukiwanie wszerz odnajdzie je niezależnie od grafu.