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

Question

El problema que intento 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 BFS para buscar todos los puntos, pero mi principal preocupación es que, a pesar de que BFS encuentra el punto correctamente, ¿cómo puedo conocer su camino?

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 tiene que visitar cuando la cola visitada se llena con todos los nodos que BFS ha buscado?

Answer 1

Para ello, es necesario almacenar una map:V->V [de vértices a los vértices], que trazará un mapa de cada nodo v, el vértice u que "descubrió" v.

Va a completar este mapa durante las iteraciones de BFS.

tarde - se puede reconstruir la ruta simplemente yendo desde el nodo de destino [en el mapa] - hasta hasta llegar de nuevo a la fuente, y es yor camino [revertido, por supuesto ...]

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