DFS can also be described non-recursively (via a stack):
visited[] // array of visiting orders, indexed by vertex 0..nV-1
findPathDFS(G,src,dest):
| Input graph G, vertices src,dest
|
| forall vertices v∈G do
| visited[v]=-1
| end for
| found=false
| visited[src]=src
| push src onto new stack s
| whilefound ∧ s is not empty do
| | pop v from s
| | if v=dest then
| | found=true
| | else
| | | foreach (v,w)∈edges(G) such that visited[w]=-1 do
| | | visited[w]=v
| | | push w onto s
| | | end for
| | end if
| end while
| if found then
| display path in dest..src order
| end if
Uses standard stack operations (push, pop, check if empty)
Time complexity is the same: O(V+E) (each vertex added to stack once, each element in vertex's adjacency list visited once)
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}
found ∧ s is not empty do
| | pop v from s
| | if v=dest then
| | found=true
| | else
| | | for each (v,w)∈edges(G) such that visited[w]=-1 do
| | | visited[w]=v
| | | push w onto s
| | | end for
| | end if
| end while
| if found then
| display path in dest..src order
| end if