[prev] 66 [next]

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)