¿Cómo obtener la ruta entre 2 nodos usando la búsqueda de primer orden?

Question

Estoy tratando de encontrar una ruta entre dos nodos en un gráfico, donde los bordes son sin ponderar.

Estoy utilizando un Breadth First Search, que se detiene cuando encuentra el destino, con el fin de encontrar la existencia de una ruta, pero no estoy seguro de cómo obtener la ruta en sí.

Intenté mirar la lista de nodos visitados, pero esto no pareció ayudar. Vi a alguien responder esta pregunta usando prolog, pero soy un programador de C++.

También miré en Dijkstras algorithm, pero esto parece más de matar, ya que una simple búsqueda en Breadth-first me consiguió casi todo el camino.

¿Cómo obtener la ruta entre 2 nodos utilizando la búsqueda de primer orden?

Answer 1

En su estructura de nodo, agrega una variable llamada parentNode que es la principal de ese nodo en la ruta. Al final, puede recuperar la ruta al atravesar desde el nodo objetivo hacia atrás.