Comment puis-je trouver le chemin réel trouvé par BFS?

Le problème, je vais essayer de résoudre les préoccupations de l'arbre de système MRT.

Chaque nœud peut être connecté à 4 points au maximum, ce qui simplifie chose de beaucoup. Voici ma pensée.

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

Je peux écrire du code pour enregistrer toutes les informations dont j'ai besoin pour BFS à la recherche pour tous les points, mais mon principal souci, c'est que, même si BFS trouve le point correctement, comment puis-je savoir son chemin?

BFS recherche à chaque niveau, et lorsque l'une d'elle atteint ma destination, il sautera de l'exécution de la boucle, et puis, je vais avoir visité la file d'attente et un inconnu file d'attente, comment suis-je censé dire à l'utilisateur ce qu'il s'arrête il a besoin pour visiter lors de la visité de la file d'attente est remplie avec tous les nœuds de la BFS a cherché?

source d'informationauteur Shane Hsu

  1. 20

    Pour ce faire, vous avez besoin de stocker un map:V->V (les sommets aux sommets), qui va de la carte à partir de chaque nœud vle sommet u qui a "découvert" v.

    Vous allez remplir cette carte pendant les itérations de BFS.

    Plus tard, vous pouvez reconstruire le de chemin en allant simplement à partir du nœud cible (à la carte) jusqu'à ce que vous obtenez de retour à la source, qui sera votre chemin (inversé, bien sûr).

    Noter que cette carte peut être mis en œuvre comme un tableau si vous énumérer les sommets.