graph breadth first search code example

Example 1: python breadth first search

# tree level-by-level traversal. O(n) time/space
def breadthFirstSearch(root):
    q = [root]

    while q:
        current = q.pop(0)
        print(current)
        if current.left is not None: q.append(current.left)
        if current.right is not None: q.append(current.right)

Example 2: 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 3: 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)
               }
           }
       }
   }