Отслеживание и возвращение пути в глубину Первый поиск

Ответ 1

Вы правы - вы не можете просто вернуть стек, он действительно содержит много невидимых узлов.

Однако, поддерживая карту (словарь): map:Vertex->Vertex такой, что parentMap[v] = the vertex we used to discover v, вы можете получить свой путь.

Модификация, которую вам нужно будет сделать, в значительной степени находится в цикле for:

    for child in children:
        stack.push(child[0])
        parentMap[child] = parent #this line was added

Позже, когда вы нашли свою цель, вы можете получить путь от источника к цели (псевдокод):

curr = target
while (curr != None):
  print curr
  curr = parentMap[curr]

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

Я однажды ответил на аналогичный (хотя и не идентичный ИМО) вопрос относительно нахождения фактического пути в BFS в этой теме

Другим решением является использование рекурсивной версии DFS, а не итеративного + стека, и как только цель будет найдена, распечатайте все узлы current в резервной копии рекурсии - но это решение требует редизайна алгоритма для рекурсивного один.

P.S. Обратите внимание, что DFS может не найти путь к цели (даже если поддерживается набор visited), если граф содержит бесконечную ветвь.
Если вы хотите, чтобы полный (всегда находит решение, если он существует) и оптимальный алгоритм (находит самый короткий путь), вы можете использовать BFS или Итеративное углубление DFS или даже A * Алгоритм если у вас есть эвристическая функция

Ответ 2

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

http://www.python.org/doc/essays/graphs/

Ответ 3

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

Пример:

     A
   /    \
  C      B
  \     / \
   \    D E
    \    /
       F


graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}




def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    visited = set()
    while stack:
        (vertex, path) = stack.pop()
        if vertex not in visited:
            if vertex == goal:
                return path
            visited.add(vertex)
            for neighbor in graph[vertex]:
                stack.append((neighbor, path + [neighbor]))

print (dfs_paths(graph, 'A', 'F'))   #['A', 'B', 'E', 'F']

Ответ 4

Я только что реализовал нечто подобное в PHP.

Основная идея заключается в следующем: зачем мне поддерживать другой стек, когда есть стек вызовов, который в каждой точке исполнения отражает путь, полученный из точки входа. Когда алгоритм достигает цели, вам просто нужно вернуться к текущему стеку вызовов, что приводит к прочтению пути, сделанного в обратном направлении. Вот модифицированный алгоритм. Обратите внимание на разделы return immediately.

/**
 * Depth-first path
 * 
 * @param Node $node        Currently evaluated node of the graph
 * @param Node $goal        The node we want to find
 *
 * @return The path as an array of Nodes, or false if there was no mach.
 */
function depthFirstPath (Node $node, Node $goal)
{
    // mark node as visited
    $node->visited = true;

    // If the goal is found, return immediately
    if ($node == $goal) {
        return array($node);
    }

    foreach ($node->outgoing as $edge) {

        // We inspect the neighbours which are not yet visited
        if (!$edge->outgoing->visited) {

            $result = $this->depthFirstPath($edge->outgoing, $goal);

            // If the goal is found, return immediately
            if ($result) {
                // Insert the current node to the beginning of the result set
                array_unshift($result, $node);
                return $result;
            }
        }
    }

    return false;
}