[prev] 11 [next]

Depth-first Search (cont)

Recursive DFS path checking

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
|
|  return dfsPathCheck(G,src,dest)

dfsPathCheck(G,v,dest):
|  mark v as visited
|  for all (v,w)∈edges(G) do
|  |  if w=dest then       // found edge to dest
|  |     return true
|  |  else if w has not been visited then
|  |     if dfsPathCheck(G,w,dest) then
|  |        return true    // found path via w to dest
|  |     end if
|  |  end if
|  end for
|  return false            // no path from v to dest