Coding Interview Club

Prepare for coding interviews in simple and structured steps

Breadth First Search (BFS) Graph Algorithm

Category: 
Problem: 

Provide Breadth First Search (BFS) Graph Algorithm

Approach: 

Breadth First Search (BFS) is a graph traversal algorithm where we scan the nodes level by level i.e. we visit each of a node n’s adjacent nodes before searching any of n's grand children.

Solution: 

void search (Node root){

  Queue queue = new Queue();

  visit(root);

  root.visited = true;

  Queue.enqueue (root);

 

  while (!queue.isEmpty()) {

    Node r = queue.dequeue();

    For each (Node n in r.adjacent){

      if (n.visited == false) {

        visit(n);

        n.visited = true;

        queue.enqueue(n);

      }

    }

  }

}

 

Unlike trees, Grahs nodes can have path to any other node even forming cycles. Hence, when working with Graph, we must also check if the node has been already visited to avoid infinite loops. In our BFS algorithm we check this using the visited flag. 

Back to Top