Восстановление пути в поиске в ширину (BFS) используется когда необходимо определить сам путь от начальной вершины до конечной вершины в графе или дереве. Обычно это делается с использованием списка предков (например prev). Идея заключается в том, чтобы хранить список предков для каждой вершины в процессе выполнения BFS.
prev[i] - хранит номер вершины, из которой мы попадаем в вершину i.
Сохранение вершины, из которой мы попадаем в смежную вершину можно организовать таким образом:
prev[смежная_вершина] = текущая_вершина
Для восстановления пути необходимо пройтись по данному массиву с конца до стартовой вершины, выписывая все вершины в какой-либо список. По окончании этого процесса, список необходимо перевернуть.
