Przeszukiwanie grafu

Napisałem program w Javie przeszukujący graf (DFS i BFS). Pisząc posługiwałem się wyjaśnieniem z tego źródła: http://www.algorytm.org/algorytmy-grafowe/przeszukiwanie-grafu-wszerz-bfs-i-w-glab-dfs.html
Gdy skończyłem sprawdziłem działanie dla podanego przykładu i wszystko działało więc byłem pewien, że program działa poprawnie. Teraz jednak mam pewne wątpliwości...
Czy może ktoś zerknąć na ten przykład BFS na stronie którą podałem? W drugim kroku jest taki fragment:

Odwiedzone: 1, 2; Kolejka: 3, 4, 5;
Bierzemy wierzchołek z kolejki, odwiedzamy go, jedynym następnikiem 3 jest 6 więc wrzucamy go do kolejki:

Patrząc na rysunek i grafu widzę jednak, że wierzchołek nr 3 ma oprócz 6 także następnik 4. 4 nie jest oznaczona jeszcze jako odwiedzony znajduje się tylko w kolejce... czy jeśli dany wierzchołek nie był jeszcze oznaczony a jest jedynie w kolejce to i tak już go pomijamy nie trzeba dodać go do kolejki po raz drugi?
Z góry dzięki za pomoc.

Oznaczasz wierzchołki w chwili wrzucania do kolejki a nie w chwili "obslugiwania" danego wierzchołka.

W algorytmie przeszukiwania grafu ważonego Dijkstry jest inaczej. Wierzchołek idzie do kolejki priorytetowej i jest zaznaczany jako odwiedzony dopiero wtedy gdy wyjdzie z kolejki mając najniższą wagę. Dzięki temu można wierzchołek wielokrotnie odwiedzać różnymi drogami dla porównania która droga jest szybsza. Wtedy może nastąpić zmiana drogę rozwiązania.