Comment obtenir le chemin d'accès entre 2 nœuds à l'aide de Largeur tout d'Abord de Recherche?

Je suis en train d'essayer de trouver un chemin entre deux nœuds dans un graphe, où les bords sont brute.

Je suis à l'aide d'un Largeur de Recherche, qui s'arrête lorsqu'il trouve la cible, afin de trouver l'existence d'un chemin d'accès, mais je ne suis pas sûr de la façon d'obtenir le chemin lui-même.

J'ai essayé de regarder la liste des nœuds visités, mais cela ne semble pas aider.
J'ai vu quelqu'un pour répondre à cette question à l'aide de prolog, mais je suis un programmeur C++.

J'ai aussi regardé Dijkstras algorithm, mais cela semble être de plus de tuer, puisqu'une simple Étendue-première Recherche m'a fait presque tout le chemin.

Comment obtenir le chemin d'accès entre 2 nœuds à l'aide de Largeur tout d'Abord de Recherche?

OriginalL'auteur cleerline | 2011-03-01

  1. 22

    Dans votre struct nœud, vous ajoutez une variable appelée parentNode qui est le parent de ce nœud dans le chemin d'accès. En fin de compte, vous pouvez récupérer le chemin d'accès par la traversée de l'objectif nœud en arrière.

    Je pense que cette approche pourrait fonctionner pour les arbres, mais pas pour les graphes, où un nœud peut avoir plusieurs parents. Dans ce cas, nous pourrions avoir besoin de maintenir une liste que le chemin est construit.

    OriginalL'auteur Thuy