Depth-first Search(DFS)

There are generally two methods to write DFS algorithm, one is using recursion, another one is using stack. （reference from Wiki Pedia）

Pseudocode for both methods:

A recursive implementation of DFS:

1 procedure DFS(G,v):
2       label v as discovered
3       for all edges from v to w in G.adjacentEdges(v) do
4           if vertex w is not labeled as discovered then
5               recursively call DFS(G,w)

A non-recursive implementation of DFS(using stack):

1   procedure DFS-iterative(G,v):
2       let S be a stack
3       S.push(v)
4       while S is not empty
5             v ← S.pop() 
6             if v is not labeled as discovered:
7                 label v as discovered
8                 for all edges from v to w in G.adjacentEdges(v) do
9                     S.push(w)

The non-recursive implementation is similar to breadth-first search but differs from it in two ways: it uses a stack instead of a queue, and it delays checking whether a vertex has been discovered until the vertex is popped from the stack rather than making this check before pushing the vertex.

Depth-first Search(DFS),布布扣,bubuko.com

Depth-first Search(DFS)

原文：http://www.cnblogs.com/EdwardLiu/p/3781128.html