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.
0
0
BFS jest lepszy do tego o czym piszesz. I nie rozumiem jaki jest problem bo napisanie BFSa bez stosu jest trywialne.
0
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ą).
0
Chcesz powiedzieć że zrobiłeś BFS w postaci rekurencyjnej zaś w postaci iteracyjnej nie potrafisz?
0
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.
1
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.
1
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.
0
dobra, właśnie nie wiedziałem jak zrobić z tą informacją o rodzicu, dzięki - będę coś działał