Как получить путь между двумя узлами, используя поиск в ширину?

Question

Я пытаюсь найти путь между двумя узлами в графе , где ребра невзвешенные .

Я использую Поиск в ширину , который останавливается, когда он находит цель, чтобы найти существование пути, но я не уверен, как получить сам путь.

Я попытался просмотреть список посещенных узлов, но это, похоже, не помогло. Я видел, как кто-то ответил на этот вопрос, используя пролог, но я программист на C ++.

Я также посмотрел на Dijkstras algorithm, но это похоже на убийство, так как простой поиск в ширину получил меня почти весь путь.

Как получить путь между двумя узлами с помощью поиска в ширину?

Answer 1

В структуре вашего узла вы добавляете переменную с именем parentNode, которая является родителем этого узла в пути.В конце концов, вы можете получить путь, пройдя от узла цели назад.