Модуль: Графы. BFS - обход в ширину


Задача

4 /17


Путь

Теория Нажмите, чтобы прочитать/скрыть

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

Сохранение вершины, из которой мы попадаем в смежную вершину можно организовать таким образом:

prev[смежная_вершина] = текущая_вершина
Для восстановления пути необходимо пройтись по данному массиву с конца до стартовой вершины, выписывая все вершины в какой-либо список. По окончании этого процесса, список необходимо перевернуть.

Задача

В неориентированном графе требуется найти минимальный путь между двумя вершинами. 
 
Формат входных данных
В первой строке записано число N - количество вершин в графе (1 <= N <= 100). В следующих строках задана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). В последней строке записаны номера двух вершин - начальной и конечной.
 
Формат выходных данных
Выведите сначала L - длину пути (количество ребер, которые нужно пройти). Затем выведите L+1 число - вершины в порядке следования вдоль этого пути. Если пути не существует, выведите одно число -1.
 
Примеры
№ Входные данные Выходные данные
1
5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5
 3
3 2 1 5

time 1000 ms
memory 32 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w64172
Free Pascal1
Python283
Комментарий учителя

Напишите программу

или выберите язык программирования и введите исходный код

Auto

       

Результат проверки программы 
Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!