Cześć, Próbuję napisać algorytm do przeszukiwania grafu wszerz w celu znalezienia ścieżki (najkrótszej) z wierzchołka o indeksie 1 do wierzchołka o indeksie 0. Napisałem sam algorytm BFS, który działa bez zarzutu i dociera do wierzchołka 0, ale nie potrafię uzupełnić go o zapisywanie znalezionej ścieżki. Właściwie to udało mi się to zrobić, ale algorytm dla niekórych grafów kończy działanie wyjątkiem std::bad_alloc.
Poniżej samo BFS, które działa bez zarzutu:
https://4programmers.net/Pastebin/14635
Poniżej algorytm z zapamiętywaniem ścieżki:
https://4programmers.net/Pastebin/14636
A poniżej cały program:
https://4programmers.net/Pastebin/14640
Ponieważ na początku program konstruuje graf na podstawie danej wejściowej, oznaczyłem miejsce, w któym zaczynam przeszukiwać. Algorytm nie działą np. dla danej wejściowej 999. Wydaje mi się, że po prostu przekraczam limit pamięci. Czy da się jakoś ten problem rozwiązać?
Żeby zarysować kontekst dodam, że ten algorytm ma rozwiązywać następujący problem:
https://szkopul.edu.pl/problemset/problem/rUp0jP53SVTkXkSewiZQvKI6/site/?key=statement
0
1
- Nie zwalniasz pamięci, którą zalakowałeś przy pomocy new. W ogóle te alokacje przy pomocy new są tam niepotrzebne.
- Wystarczy trzymać wierzchołek poprzedni dla każdego odwiedzonego wierzchołka. Żeby odzyskać ścieżkę, trzeba przejść ją w odwrotnej kolejności, tzn. od ostatniego wierzchołka na ścieżce do wierzchołka przedostatniego i tak dalej.
0
@nalik: Dzięki za odpowiedź, rzeczywiście niepotrzebnie to skomplikowałem. Rozwiązałem tak jak napisałeś i działa. Co do alokowania za pomocą new, kompilator w VS mi nie pozwala na utworzenie tablicy o wielkości określonej zmienną, dlatego tak robię.
0
To Użyj czegoś z STL, jako "adjacency list" np., mapa: int, vector<int>, albo vector<vector<int>>.