breadth first search algorithm big O code example

Example 1: breadth first search

procedure BFS(G, start_v) is
2      let Q be a queue
3      label start_v as discovered
4      Q.enqueue(start_v)
5      while Q is not empty do
6          v := Q.dequeue()
7          if v is the goal then
8              return v
9          for all edges from v to w in G.adjacentEdges(v) do
10             if w is not labeled as discovered then
11                 label w as discovered
12                 w.parent := v
13                 Q.enqueue(w)

Example 2: bfs algorithm

function breadthFirstSearch (Start, Goal)
   { 
       enqueue(Queue,Start)
       setVisited(start)
       while notEmpty(Queue)
       {
           Node := dequeue(Queue)
           if Node = Goal
           {
               return Node
           }
           for each Child in Expand(Node)
           {
               if notVisited(Child)
               {              
                   setVisited(Child)
                   enqueue(Queue, Child)
               }
           }
       }
   }

Tags:

Cpp Example