Trusted answers to developer questions

What is Breadth First Search?

Educative Answers Team

Free System Design Interview Course

Get Educative's definitive System Design Interview Handbook for free.

The Breadth First Search (BFS) is an algorithm for traversing or searching tree or graph data structures. It explores all the nodes at the present depth before moving on to the nodes at the next depth level.

Note: It can be implemented using a queue.

The algorithm

Here are the steps for the BFS algorithm:

  • Pick a node and enqueue all its adjacent nodes into a queue.

  • Dequeue a node from the queue, mark it as visited and enqueue all its adjacent nodes into a queue.

  • Repeat this process until the queue is empty or you meet a goal.

The program can be stuck in an infinite loop if a node is revisited and was not marked as visited before. Hence, prevent exploring nodes that are visited by marking them as visited.


We have a directed graph of five nodes with G being the node to be searched. The nodes will be marked as visited using the visited array while adjacent nodes will be added to the queue.

1 of 7


Starting from the source node A, we keep exploring down the branches in an ordered fashion i.e. from A to B to C where the level completes. Then we go to the next level and explore D and G.

Time complexity

The time complexity of BFS if the entire tree is traversed is O(V)O(V) where V is the number of nodes. In the case of a graph, the time complexity is O(V+E)O(V + E) where V is the number of vertexes and E is the number of edges.


data structures
graph traversal
Copyright ©2023 Educative, Inc. All rights reserved
Trusted Answers to Developer Questions

Related Tags

data structures
graph traversal
Keep Exploring
Related Courses