Depth-first Search (cont)
DFS can also be described non-recursively (via a stack):
hasPath(G,src,dest):
| Input graph G, vertices src,dest
| Output true if there is a path from src to dest in G,
| false otherwise
|
| mark all vertices in G as unvisited
| push src onto new stack s
| found=false
| while not found and s is not empty do
| | pop v from s
| | mark v as visited
| | if v=dest then
| | found=true
| | else
| | | for each (v,w)∈edges(G) such that w has not been visited
| | | push w onto s
| | | end for
| | end if
| end while
| return found
|
Uses standard stack operations (push, pop, check if empty)
Time complexity is the same: O(V+E)
|