Skip to main content
Practice

What is Breadth-First Search (BFS)?

Breadth-First Search is an algorithm used to explore nodes in a graph or a tree, starting from one node and exploring in a level-by-level manner.


Keywords​

  • Queue: BFS uses a queue to manage nodes that need to be visited.

  • Level-order exploration: BFS explores nodes level by level for each adjacent node.

  • Shortest path: BFS is often used to find the shortest path from the start node to the target node.

  • Time complexity: (O(|V| + |E|)), where (|V|) is the number of vertices and (|E|) is the number of edges.


Step-by-step Process of BFS​

  1. Select a Node: Choose the node to start the exploration.

  2. Visit and Explore: Visit the selected node and add adjacent nodes to the queue.

  3. Level-Order Exploration: Dequeue a node, visit it, and add its adjacent nodes to the queue.

  4. Complete Exploration: End the exploration when the queue is empty.


Characteristics of BFS​

  • Breadth-First: Explores nodes of each level before moving on to nodes of the next level.

  • Layered Search: Visits nodes level by level, prioritizing nodes of the same level.

  • Shortest Path Search: BFS is effective in finding the shortest path from the start node to the target node in an undirected graph.

  • Exploration Order: The order of node exploration can vary depending on the implementation of the queue and the starting node.


Advantages and Disadvantages of BFS​

  • Advantages: Effective for finding the shortest path and visits all nodes of each level. Breadth-First Search works well even in graphs with cycles.

  • Disadvantages: BFS can use more memory than DFS as it needs to store all adjacent nodes, which can be burdensome in large graphs.

Want to learn more?

Join CodeFriends Plus membership or enroll in a course to start your journey.