深度优先 广度优先

visited[] // store previously visited node, for each vertex 0 .. nV-1

findPath (G, src, dest):
   Input graph G, vertices src, dest

   for all vertices v ∈ G do
      visited[v] =- 1
   end for
   visited[src]=src // starting node of the path
   if dfsPathCheck (G, src, dest) then // show path in dest .. src order
      v=dest
      while v≠src do
         print v"-"
         v=visited[v]
      end while
      print src
   end if

dfsPathCheck (G, v,dest):
   if v=dest then
      return true // found edge from v to dest
   else
      for all (v, w) Eedges (G) do
         if visited[w] =- 1 then
            visited[w]=v 
            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

hasPath(G,src,dest):
   Input graph G, vertices src,dest
   Output true if there is a path from src to dest in G, otherwise return false

   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 do
            push w onto s
         end for
      end if 
   end while
   return found

hasPath(G,src,dest):
   Input graph G, vertices src,dest
   Output true if there is a path from src to dest in G, otherwise return false

   mark all vertices in G as unvisited 
   if src=dest then
      return true
   end if

   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 
      for each (v,w) ∈ edges(G) such that w has not been visited
         if w=dest then
            return true
         end if
         push w onto s
      end for
   end while
   return false

mark all vertices as unvisited
if src=dest then
   return true
end if
enqueue src into a new queue Q
while Q is not empty do
   dequeue v from Q and mark v as visited
   for each edge (v,w) such that w has not been visited do
      if w=dest then
         return true
      end if
      enqueue w into Q
   end for
end while
return false

visited[]

findPathBFS(G,src,dest):
   Input graph G, vertices src,dest

   for all vertices v ∈ G do
      visited[v]=-1
   end for

   enqueue src into new queue q
   visited[src]=src
   found=false
   while not found and q is not empty do
      dequeue v from q
      if v=dest then
         found=true
      else
         for each (v,w) ∈ edges(G) such that visited[w]=-1 do
            enqueue w into q
            visited[w]=v
         end for 
      end if
   end while

   if found then 
      display path in dest...src order
   end if