形式的には、深さ優先探索は、探索対象となる木の最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。非再帰的な実装では、新しく見つかったノードはスタックに貯める。
def depthFirstSearch( start, goal ):
stack = Stack()
start.setVisited()
stack.push( start )
while not stack.empty():
node = stack.top()
if node == goal:
return stack # stack には2頂点間の経路が入っている
else:
child = node.findUnvisitedChild()
if child == none:
stack.pop()
else:
child.setVisited()
stack.push( child )
