Breadth-first Search (cont)
BFS algorithm (records visiting order, marks vertices as visited when put on queue):
visited[] // array of visiting orders, indexed by vertex 0..nV-1
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
|
Uses standard queue operations (enqueue, dequeue, check if empty)
|