Используйте список смежности и BFS. При первом посещении вершины сохраните её предка; достигнув B, пройдите по предкам назад и разверните список.
Как представить маршрут графом и восстановить путь BFS
Используйте список смежности и BFS. При первом посещении вершины сохраните её предка; достигнув B, пройдите по предкам назад и разверните список.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Есть невзвешенный граф дорог между городами. Требуется кратчайший по числу дорог путь из A в B. Как хранить граф и восстановить ответ после обхода?
Ответ
Используйте список смежности и BFS. При первом посещении вершины сохраните её предка; достигнув B, пройдите по предкам назад и разверните список.
Вершину отмечайте посещённой при постановке в очередь, чтобы не добавлять её многократно. Если B не посещена, маршрута нет. Для неориентированной дороги добавьте оба направления. Сложность обхода O(V+E), память O(V+E) с учётом хранения графа. Для взвешенных дорог обычный BFS уже не гарантирует минимальную стоимость.