Verfolgen und Zurückgeben eines Pfads in der Tiefensuche

Ich habe gerade etwas Ähnliches in PHP implementiert.

Die Grundidee dahinter lautet wie folgt: Warum sollte ich einen anderen Stapel verwalten, wenn es den Aufrufstapel gibt, der an jedem Punkt der Ausführung den Pfad vom Einstiegspunkt widerspiegelt? Wenn der Algorithmus das Ziel erreicht, müssen Sie lediglich auf dem aktuellen Aufrufstapel zurückfahren, wodurch der zurückgelegte Pfad gelesen wird. Hier ist der modifizierte Algorithmus. Beachten Sie die Abschnitte 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;
}

Nicht spezifisch für Ihr Problem, aber Sie können diesen Code optimieren und auf verschiedene Szenarien anwenden. Tatsächlich können Sie dafür sorgen, dass der Stapel auch den Pfad enthält.

Beispiel:

     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']

Dieser Link sollte Ihnen sehr helfen ... Es ist ein langer Artikel, der ausführlich über eine DFS-Suche spricht, die einen Pfad zurückgibt ... und ich denke, es ist besser als jede Antwort, die ich oder jemand anderes posten kann

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