BFS - znajdowanie drogi w grafie

Zrobiłem program, który przeszukuje graf zgodnie z algorytmem BFS. Jednak chcę bez użycia rekurencji, a jedynie kolejki lub stosu znaleźć drogę między dwoma wierzchołkami (niekoniecznie najkrótszą).
Graf mam przechowywany w postaci głównej listy z nazwami wierzchołków, która przechowuje także wskaźniki do list z wierzchołkami sąsiednimi do danego wierzchołka. Zastanawiam się, czy może lepiej byłoby użyć DFSa.

BFS jest lepszy do tego o czym piszesz. I nie rozumiem jaki jest problem bo napisanie BFSa bez stosu jest trywialne.

Właśnie piszę o BFS, którego też użyłem i który mi przechodzi przez graf, ale chcę aby znajdował mi też drogę między dwoma wierzchołkami (niekoniecznie najkrótszą).

Chcesz powiedzieć że zrobiłeś BFS w postaci rekurencyjnej zaś w postaci iteracyjnej nie potrafisz?

Potrafię zrobić bez rekurencji, ale nie wiem co zrobić, jeśli chodzi o znajdowanie drogi, jak i kiedy dodawać wierzchołki, które prowadzą do docelowego wierzchołka.

Zrób sobie klasę która przechowuje informacje o "poprzedniku" i o aktualnym polu i obekty takich klas odkładaj sobie w jakiejś kolejce. Tzn:

• do listy wierzchołków do odwiedzenia wrzucasz sobie pierwszy wierzchołek
• pętelka: wyciagamy z listy wierzchołków wierzchołek najwcześniej dodany (FIFO) i jeśli nie jest końcowym węzłem to dla każdego jego dziecka które nie jest odwiedzone:
  • wrzucamy do listy wierzchołków do odwiedzenia dziecko razem z informacją o jego "rodzicu" (wierzcholku z którego przyszliśmy,czyli tego którego przed chwilą wyciągaliśmy z kolejki)
• jeśli wyciągnięty wierzchołek jest węzłem końcowym to robimy sobie odczytywanie drogi:
  • bierzemy parenta węzła końcowego, następnie jego parenta następnie jego parenta .... aż dojdziemy do wierzchołka początkowego.

Dodam jeszcze jeden myk: - jako wierzchołek początkowy przyjmij wierzchołek który chcesz mieć na końcu drogi, wtedy ścieżka będzie prowadziła od początkowego do końcowego.

dobra, właśnie nie wiedziałem jak zrobić z tą informacją o rodzicu, dzięki - będę coś działał