Come posso trovare il percorso effettivo trovato da BFS?

Question

Il problema che sto cercando di risolvere riguarda un albero del sistema MRT.

Ogni nodo può essere collegato a 4 punti al massimo, cosa che semplifica di molto. Ecco il mio pensiero

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

posso scrivere il codice per salvare tutte le informazioni che mi servono per BFS per la ricerca di tutti i punti, ma la mia preoccupazione principale è che, anche se BFS trova il punto corretto, come faccio a sapere il suo percorso?

BFS cercherà ogni livello, e quando uno di questi raggiunge la mia destinazione, salterà fuori dal ciclo di esecuzione, e poi, otterrò una coda visitata e una coda non visitata, come dovrei dire all'utente cosa deve interrompere la visita quando la coda visitata viene riempita con tutti i nodi cercati da BFS?

Answer 1

Per fare ciò, è necessario memorizzare una map:V->V [da vertici a vertici], che mappa da ogni nodo v, il vertice u che "scoprì" v.

Questa mappa verrà popolata durante le iterazioni di BFS.

Più tardi - è possibile ricostruire il percorso semplicemente andando dal nodo di destinazione [nella mappa] - up fino a tornare alla fonte, ed è yor percorso [invertito, naturalmente ...]

Si noti che questa mappa può essere implementata come una matrice, se si enumerano i vertici.