Como posso encontrar o caminho real encontrado pelo BFS?

O problema que estou tentando resolver diz respeito a uma tree do sistema MRT.

Cada nó pode ser conectado a 4 pontos no máximo, o que simplifica muito. Aqui está o meu pensamento.

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

Eu posso escrever código para salvar todas as informações necessárias para o BFS procurar por todos os pontos, mas minha principal preocupação é que, mesmo que o BFS encontre o ponto corretamente, como posso saber seu caminho?

O BFS irá procurar cada nível, e quando um deles chegar ao meu destino, ele sairá do loop de execução e, em seguida, eu terei uma fila visitada e uma fila não visitada, como devo dizer ao usuário o que ele precisa parar para visitar quando a fila visitada é preenchida com todos os nós pesquisados ​​pelo BFS?

Para fazer isso, você precisa armazenar um map:V->V (de vértices para vértices), que mapeará de cada nó v , o vértice u que “descobriu” v .

Você irá preencher este mapa durante as iterações do BFS.

Mais tarde – você pode reconstruir o caminho simplesmente indo do nó de destino (no mapa) até você voltar para a fonte, que será o seu caminho (invertido, é claro).

Note que este mapa pode ser implementado como um array se você enumerar os vértices.