Как я могу найти фактический путь, найденный BFS?

Question

Проблема, которую я пытаюсь решить, связана с деревом системы MRT.

Каждый узел может быть подключен максимум к 4 точкам, что значительно упрощает процесс.Вот моя мысль.

struct stop {
    int path, id;
    stop* a;
    stop* b;
    stop* c;
    stop* d;
};

Я могу написать код, чтобы сохранить всю информацию, необходимую для BFS для поиска всех точек, но моя главная проблема заключается в том, что, хотя BFS находит точку правильно, как можноЯ знаю его путь?

BFS будет искать каждый уровень, и когда один из них достигнет моего пункта назначения, он выпрыгнет из цикла выполнения, а затем я получу посещенную очередь и непосещенную очередь, какя должен сообщить пользователю, какие остановки ему нужно посетить, когда посещенная очередь заполнена всеми узлами, которые BFS искала?

Answer 1

Для этого вам нужно сохранить map:V->V (от вершин до вершин), который будет отображать из каждого узла v, вершину u, которая «обнаружила» v.

Вы будете заполнять эту карту во время итераций BFS.

Позже - вы можете восстановить путь, просто пройдя от целевого узла (на карте) до тех пор, пока не вернетесь к источнику, который будет вашим путем (конечно, в обратном направлении).

Обратите внимание, что эту карту можно реализовать в виде массива, если вы перечислите вершины.