Can a depth-first search using a stack return a path to the goal?

I'd like to use a stack and return a path, but I'm thinking it's not possible.

A node must be called directly by its parent so that it can receive the path behind it, whereas when this node is pushed onto a stack, it loses the path so far. Using a stack would result in a node being evaluated in isolation, and I couldn't pass the path to the node's parent through to the node.

I can't let nodes have the property of the path behind them, since it's a homework assignment.

I开发者_JAVA百科've been stumped on this one for over a week!

---

Whenever you pop a node from the stack, you need a way of retrieving the path that led to that node.

One solution is push tuples of (node, path) on the stack instead of just node values. If path is a purely functional list like in Haskell, this is a good solution, but in Python it may not be as idiomatic. Also while the path strictly speaking isn't stored within the node, this solution probably isn't in the spirit of the question.

Another solution is to maintain a separate stack that contains the path to the previously visited node. The depth-first stack contains tuples of (node, depth) where depth is the depth of the node in the search. Before adding node to the end of the path, elements are popped from the path until the length of the path equals depth.

---

"A node must be called directly by its parent so that it can receive the path behind it," <- This seems okay.

whereas when this node is pushed onto a stack, it loses the path so far. <- This isn't anything to worry about I believe.

What you can do is to recursively build up the stack with something like

def makepath(someGraph, from, to):
    if(from == to)
        return ""

    nextNode= <...> #find out next node in path here
    return makepath(someGraph, nextNode, to) + str(nextNode)