BFS stands for Breadth-First Search. It is a graph traversal algorithm used to explore or search through all the vertices of a graph in breadth-first order, i.e., exploring all vertices at the same depth level before moving to vertices at the next depth level.

Here’s a step-by-step explanation of how BFS works:

1. Start with a source vertex or node in the graph.
2. Visit the source vertex and enqueue it into a queue.
3. While the queue is not empty, do the following:

3. Dequeue a vertex from the queue.
4. Process or visit the dequeued vertex.
5. Enqueue all the adjacent vertices of the dequeued vertex that have not been visited yet.
6. Mark the dequeued vertex as visited.

4. If there are still unvisited vertices in the graph, select one of them as the new source vertex and repeat steps 2 to 4.
5. Repeat the process until all vertices in the graph have been visited or processed.

BFS ensures that all vertices at the same depth level from the source vertex are visited before moving to the vertices at the next depth level. This guarantees that the algorithm explores the graph in a breadth-first manner, hence the name.

BFS can be used to solve various graph-related problems, such as finding the shortest path between two vertices, determining if a graph is connected, or performing level-order traversal in a tree.

It’s important to note that BFS requires additional data structures, typically a queue, to keep track of the vertices to visit. The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph.

BFS algorithm

In this article, we will discuss the BFS algorithm in the data structure. Breadth-first search is a graph traversal algorithm that starts traversing the graph from the root node and explores all the neighboring nodes. Then, it selects the nearest node and explores all the unexplored nodes. While using BFS for traversal, any node in the graph can be considered as the root node.

There are many ways to traverse the graph, but among them, BFS is the most commonly used approach. It is a recursive algorithm to search all the vertices of a tree or graph data structure. BFS puts every vertex of the graph into two categories – visited and non-visited. It selects a single node in a graph and, after that, visits all the nodes adjacent to the selected node.

Applications of BFS algorithm

The applications of breadth-first-algorithm are given as follows –

• BFS can be used to find the neighboring locations from a given source location.
• In a peer-to-peer network, BFS algorithm can be used as a traversal method to find all the neighboring nodes. Most torrent clients, such as BitTorrent, uTorrent, etc. employ this process to find “seeds” and “peers” in the network.
• BFS can be used in web crawlers to create web page indexes. It is one of the main algorithms that can be used to index web pages. It starts traversing from the source page and follows the links associated with the page. Here, every web page is considered as a node in the graph.
• BFS is used to determine the shortest path and minimum spanning tree.
• BFS is also used in Cheney’s technique to duplicate the garbage collection.
• It can be used in ford-Fulkerson method to compute the maximum flow in a flow network.

Algorithm

The steps involved in the BFS algorithm to explore a graph are given as follows –

Step 1: SET STATUS = 1 (ready state) for each node in G

Step 2: Enqueue the starting node A and set its STATUS = 2 (waiting state)

Step 3: Repeat Steps 4 and 5 until QUEUE is empty

Step 4: Dequeue a node N. Process it and set its STATUS = 3 (processed state).

Step 5: Enqueue all the neighbours of N that are in the ready state (whose STATUS = 1) and set

their STATUS = 2

(waiting state)

[END OF LOOP]

Step 6: EXIT

Example of BFS algorithm

Now, let’s understand the working of BFS algorithm by using an example. In the example given below, there is a directed graph having 7 vertices.

In the above graph, minimum path ‘P’ can be found by using the BFS that will start from Node A and end at Node E. The algorithm uses two queues, namely QUEUE1 and QUEUE2. QUEUE1 holds all the nodes that are to be processed, while QUEUE2 holds all the nodes that are processed and deleted from QUEUE1.

Now, let’s start examining the graph starting from Node A.

Step 1 – First, add A to queue1 and NULL to queue2.

1. QUEUE1 = {A}    
2. QUEUE2 = {NULL}    

Step 2 – Now, delete node A from queue1 and add it into queue2. Insert all neighbors of node A to queue1.

1. QUEUE1 = {B, D}    
2. QUEUE2 = {A}  

Step 3 – Now, delete node B from queue1 and add it into queue2. Insert all neighbors of node B to queue1.

1. QUEUE1 = {D, C, F}    
2. QUEUE2 = {A, B}  

Step 4 – Now, delete node D from queue1 and add it into queue2. Insert all neighbors of node D to queue1. The only neighbor of Node D is F since it is already inserted, so it will not be inserted again.

1. QUEUE1 = {C, F}    
2. QUEUE2 = {A, B, D}  

Step 5 – Delete node C from queue1 and add it into queue2. Insert all neighbors of node C to queue1.

1. QUEUE1 = {F, E, G}    
2. QUEUE2 = {A, B, D, C}  

Step 5 – Delete node F from queue1 and add it into queue2. Insert all neighbors of node F to queue1. Since all the neighbors of node F are already present, we will not insert them again.

1. QUEUE1 = {E, G}    
2. QUEUE2 = {A, B, D, C, F}  

Step 6 – Delete node E from queue1. Since all of its neighbors have already been added, so we will not insert them again. Now, all the nodes are visited, and the target node E is encountered into queue2.

1. QUEUE1 = {G}    
2. QUEUE2 = {A, B, D, C, F, E}  

Complexity of BFS algorithm

Time complexity of BFS depends upon the data structure used to represent the graph. The time complexity of BFS algorithm is O(V+E), since in the worst case, BFS algorithm explores every node and edge. In a graph, the number of vertices is O(V), whereas the number of edges is O(E).

The space complexity of BFS can be expressed as O(V), where V is the number of vertices.

Books on BFS