¿Cómo puedo encontrar la ruta real encontrada por BFS?

El problema que trato de resolver se refiere a un árbol del sistema MRT.

Cada nodo se puede conectar a 4 puntos como máximo, lo que simplifica mucho las cosas. Aquí está mi pensamiento.

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

Puedo escribir código para guardar toda la información que necesito para que BFS busque todos los puntos, pero mi principal preocupación es que, aunque BFS encuentre el punto correctamente, ¿cómo puedo conocer su ruta?

BFS buscará cada nivel, y cuando uno de ellos llegue a mi destino, saltará del ciclo de ejecución, y luego, obtendré una cola visitada y una cola no visitada, ¿cómo se supone que debo decirle al usuario qué paradas necesita? para visitar cuando la cola visitada se llena con todos los nodos que BFS ha buscado?

    Para hacerlo, debe almacenar un map:V->V (de vértices a vértices), que mapeará desde cada nodo v , el vértice u que “descubrió” v .

    Va a llenar este mapa durante las iteraciones de BFS.

    Más tarde: puedes reconstruir la ruta simplemente yendo desde el nodo objective (en el mapa) hasta que vuelvas a la fuente, que será tu ruta (invertida, por supuesto).

    Tenga en cuenta que este mapa se puede implementar como una matriz si enumera los vértices.