[prev] 72 [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
|
|  mark all vertices in G as unvisited
|  return dfsPathCheck(G,src,dest)

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