поиск в глубину — DFS кратчайший путь лабиринта в переполнении стека
У меня проблемы с выяснением, как именно заставить это работать … Я пытаюсь найти кратчайший путь к цели, используя DFS. Я знаю, что BFS лучше, но меня попросили использовать DFS для этого. Как видите, я пытаюсь сравнить все стеки, ведущие к концу, чтобы найти цель, но она не работает, когда-либо печатается только первый стек, который приводит к цели … Я знаю, где мне нужно не посетить узлы, но я не могу понять, как именно. Прямо сейчас у меня есть путь к цели, но не самый короткий. Любая помощь с этим будет принята с благодарностью.
Решение
Написание нерекурсивного DFS возможно при использовании вашего собственного стека, но я считаю, что рекурсивное решение более элегантно. Вот эскиз одного:
DFS(vertex)
path.push_back(vertex)
visited[vertex] = true
if we found the exit
output path
else
for each neighbor v of vertex
if not visited[v]
DFS(v)
visited[vertex] = false
path.pop_back()
Другие решения
Других решений пока нет …
detector