+91-8595577826

Learning basic graph traversal algorithms is important for any software developer to crack coding rounds of interviews at top tech companies.

Breadth-first search is one such graph algorithm, which helps solve easy as well as advanced graph problems. Knowing this algorithm can boost your chances of clearing tech interview questions on data structure and algorithms.

In this article, we cover everything you need to know about the BFS algorithm, including:

  • What Is Graph Traversal?
  • What Is BFS?
  • Applications of BFS
  • How Does BFS Work?
  • BFS Algorithm
  • BFS Pseudocode
  • BFS Code
  • BFS for Disconnected Graph
  • BFS vs. DFS
  • BFS FAQs

What Is Graph Traversal?

Graph traversal is the process of visiting every vertex and edge of a graph at least once. The order in which the vertices are visited is important. There may be many such orders, but the challenge is to find the traversal technique best suited to solve a particular problem.

What Is BFS?

Breadth-first search (BFS) is a graph search and traverse algorithm used to solve many programming and real-life problems. It follows a simple, level-based approach. We can easily solve many problems in computer science by modeling them in terms of graphs. For example: analyzing networks, mapping routes, scheduling, and more.

BFS Applications

  • Finding the shortest path: In an unweighted graph, the shortest path between two nodes is the path with the least number of edges. BFS can be used to find the shortest path between a source node and all the remaining nodes in an unweighted graph.
  • Finding the minimum spanning tree: After some modifications, this algorithm can be used to find the minimum spanning tree for unweighted graphs.
  • Detecting a cycle: This algorithm can be used to detect a cycle in graphs.
  • Finding a path: We can use BFS to check whether a path exists between two nodes.
  • Peer-to-peer networks: In P2P networks, like BitTorrent, BFS is used to find all neighbor nodes.
  • Broadcasting networks: In network broadcasting, broadcasted packets are guided by the BFS algorithm to reach all target nodes.
  • GPS navigation systems: BFS is used to find all neighboring locations.
  • Search engine crawlers: The main idea behind crawlers is to start from the source page, follow all links from that source to other pages, and keep repeating the same until the objective for crawling is completed.
  • Social networking websites: We can find the number of people within a given distance "k" from a person in a social network using BFS.
  • Connected component: We can use BFS to find all the nodes within a connected component of a graph.
  • Bipartite: This algorithm can be used to check if a graph is bipartite.

How Does BFS Work?

The BFS algorithm traverses the graph across its breadth. It's a layerwise traversal algorithm. BFS starts traversing the graph from a chosen "root" node, say Source, and explores all of its neighbor nodes at its next depth before moving on to the other nodes.

Let's look at the algorithm to understand this better.

BFS Algorithm

  • Step 1: Create an empty queue to store the nodes to be visited and a boolean vector to track the visited nodes. Initially, no node is visited.
  • Step 2: Choose a starting node, mark it visited, and add it to the queue.
  • Step 3: Extract the front item of the queue, add it to the BFS order, and traverse through the list of that node's adjacent nodes.
  • Step 4: If a node in that list has not been already visited, mark it visited, and add it to the back of the queue.
  • Step 5: Keep repeating steps 3 and 4 until the queue is empty.

Let's take an example. We'll use an undirected graph with six vertices.