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
| | | | if dfsPathCheck(G,w,dest) then
| | | | return true // found path via w to dest
| | | | end if
| | | end if
| | end for
| end if
| return false // no path from v to dest
|
|