Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Tracing and Returning a Path in Depth First Search

So I have a problem that I want to use depth first search to solve, returning the first path that DFS finds. Here is my (incomplete) DFS function:

    start = problem.getStartState()
    stack = Stack()
    visited = []
    stack.push(start)
    if problem.isGoalState(problem.getStartState):
        return something
    while stack:
        parent = stack.pop()
        if parent in visited: continue
        if problem.isGoalState(parent):
            return something
        visited.append(parent)
        children = problem.getSuccessors(parent)
        for child in children:
            stack.push(child[0])

The startState and goalState variables are simply a tuple of x, y coordinates. problem is a class with a variety of methods. The important ones here are getSuccessors (which returns the children of a given state in the form of a list of 3 item tuples. for this part of the problem though, only the first element of the tuple, (child[0]), which returns the state of the child in x, y coordinates, is important) and isGoalState (which provides the x, y coordinates of the goal state).

So I THINK (difficult to test at this point), that this function, given proper implementation of everything else, will return once it has reached a goal state. Please let me know if I am missing something. My biggest issue, though, is WHAT to return. I want it to output a list of all of the states it takes to get to the goal state, in order from the beginning to the end. It doesn't seem like simply returning my stack will do the trick, since the stack will include many unvisited children. Nor will my visited list yield anything useful, since it is conceivable I could reach dead ends, have to backtrack, but still have the dead-end tuples in the visited list. How would I go about getting the list I desire?

like image 752
user1427661 Avatar asked Oct 12 '12 17:10

user1427661


People also ask

How do I trace a path in depth-first search?

Tracing the Path in Iterative Depth-First Search In one approach, after visiting a node, we memorize which node its parent is in the search tree. That way, after finding the target node, we can reconstruct the path by following the parent-child hierarchy. In the other method, we store the full path to each node.

What does depth-first search return?

Depth-first search (DFS) is an algorithm for searching a graph or tree data structure. The algorithm starts at the root (top) node of a tree and goes as far as it can down a given branch (path), then backtracks until it finds an unexplored path, and then explores it.

What is depth-first search explain it with a tracing example?

Depth First Search Example We use an undirected graph with 5 vertices. Undirected graph with 5 vertices. We start from vertex 0, the DFS algorithm starts by putting it in the Visited list and putting all its adjacent vertices in the stack. Visit the element and put it in the visited list.


4 Answers

You are right - you cannot simply return the stack, it indeed contains a lot of unvisited nodes.

However, by maintaining a map (dictionary): map:Vertex->Vertex such that parentMap[v] = the vertex we used to discover v, you can get your path.

The modification you will need to do is pretty much in the for loop:

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

Later on, when you found your target, you can get the path from the source to the target (pseudo code):

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

Note that the order will be reversed, it can be solved by pushing all elements to a stack and then print.

I once answered a similar (though not identical IMO) question regarding finding the actual path in BFS in this thread

Another solution is to use a recursive version of DFS rather then iterative+stack, and once a target is found, print all current nodes in the recursion back up - but this solution requires a redesign of the algorithm to a recursive one.


P.S. Note that DFS might fail to find a path to the target (even if maintaining a visited set) if the graph contains an infinite branch.
If you want a complete (always finds a solution if one exists) and optimal (finds shortest path) algorithm - you might want to use BFS or Iterative Deepening DFS or even A* Algorithm if you have some heuristic function

like image 84
amit Avatar answered Oct 04 '22 18:10

amit


Not specific to your problem, but you can tweak this code and apply it to different scenarios, in fact, you can make the stack also hold the path.

Example:

     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']
like image 27
XueYu Avatar answered Oct 04 '22 18:10

XueYu


this link should help you alot ... It is a lengthy article that talks extensively about a DFS search that returns a path... and I feel it is better than any answer I or anyone else can post

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

like image 24
Joran Beasley Avatar answered Oct 01 '22 18:10

Joran Beasley


I just implemented something similar in PHP.

The basic idea behind follows as: Why should I maintain another stack, when there is the call stack, which in every point of the execution reflects the path taken from the entry point. When the algorithm reaches the goal, you simply need to travel back on the current call stack, which results in reading the path taken in backwards. Here is the modified algorithm. Note the return immediately sections.

/**
 * 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;
}
like image 32
user2555221 Avatar answered Oct 04 '22 18:10

user2555221