Breadth-First Search Algorithm

A graph traversal algorithm called breadth-first search investigates every node in the graph starting with the root node. In this article, we will briefly discuss BFS algorithm.

A graph traversal algorithm called breadth-first search investigates every node in the graph starting with the root node. Then it chooses the closest node and investigates every new node. Any node in the graph can be the root node when employing BFS for traversal. In this tutorial, we will discuss the BFS algorithm in the data structure. We will talk about the algorithm followed by the BFS along with the methods to implement BFS using various programming languages. 

There are other techniques to navigate the graph, however, BFS is the method that is most frequently applied. The process of searching every vertex in a branch or graph data structure is recursive. Every vertex in the graph is divided into two groups by BFS: visited and non-visited. An individual node in a graph is chosen, and then all of the nodes next to that node are visited.

Breadth-First Search

BFS aims to investigate every node in the graph starting with the root node. Then it chooses the closest node and investigates every new node. Any node in the graph can be the root node when employing BFS for traversal. The only problem with this is that, apart from trees, graphs might have cycles, which means we might keep going back to the same node. We categorize the vertices into two groups in order to prevent processing a node twice:

• Visited node
• Unvisited node

The visited vertices are noted using a Boolean visited array. All vertices are considered to be reachable from the initial vertex for the sake of simplicity. For traversal, BFS employs a queue data structure.

Applications of BFS

• From a specific source location, BFS can be used to locate nearby sites.
• The BFS algorithm can be used as a traversal method in a peer-to-peer network to locate every adjacent node. This method is used by the majority of torrent applications, including BitTorrent, uTorrent, etc., to locate “seeds” and “peers” on the network.
• BFS can be used by web crawlers to build indexes for web pages. It is one of the most important algorithms for indexing web pages. It begins its journey on the source page and then navigates across the page’s links. Each web page is viewed in this case as a node on the graph.
• The shortest route and least spanning tree are found using BFS.
• Cheney’s method of duplicating garbage collection also employs BFS.
• It can be used to calculate the max flow in a flow system using the Ford-Fulkerson approach.

Steps for BFS

Step 1: For each node in G, set STATUS to 1 (ready status).

Enqueue the initial node A and set its STATUS to 2 in step 2 (waiting state)

Step 3: Keep going through Steps 4 and 5 until the QUEUE is empty.

Dequeue a node N in step 4. After processing it, set its STATUS to 3. (processed state).

Step 5: Put all of N’s neighbors in the queue who are ready (their STATUS = 1) and set

STATUS = 2

(Waiting State)

[END OF THE LOOP]

Step 6: Exit

Example of BFS

Let us see a BFS example below to understand the algorithm in a better manner:

Using the BFS, which begins at Node A and ends at Node E, it is possible to locate the minimal path “P” in the graph above. The algorithm employs QUEUE1 and QUEUE2 as its two queues. All nodes that need to be processed are kept in QUEUE1, and all nodes that have already been processed and removed from QUEUE1 are kept in QUEUE2.

Let’s now begin analyzing the graph, starting at Node A.

Step 1: Put A in queue 1 first, then NULL in queue 2.

QUEUE1 = {A}    

QUEUE2 = {NULL} 

Step 2: Next, move node A to queue 2 and remove it from queue 1. Add to queue1 all of node A’s neighbors.

QUEUE1 = {B, D}    

QUEUE2 = {A}  

Step 3: Add node B to queue2 and remove node B from queue1. Add all of node B’s neighbors to queue 1.

QUEUE1 = {D, C, F}

QUEUE2 = {A, B}  

Step 4: Node D should now be removed from queue 1 and added to queue 2. Add to queue1 all of node D’s neighbors. It won’t be placed again because Node D’s sole neighbor is Node F because it has already been added.

QUEUE1 = {F, E, G}    

QUEUE2 = {A, B, D, C}

Step 5: Node F is removed from queue 1 and added to queue 2. Add to queue1 all of node F’s neighbors. We won’t insert any additional neighbors for node F because they are all already there.

QUEUE1 = {E, G}    

QUEUE2 = {A, B, D, C, F}  

Step 6: Remove node E from the queue in step 6. We won’t add them again because all of its neighbors have already been included. All nodes have now been visited, and queue2 has encountered target node E.

BFS Traversal Implementation

We will implement the BFS traversal using the approach below:

• Create a queue, then insert the first vertex.
• Create a visited array from scratch and designate the first vertex as visited.
• Till the line is empty, proceed as follows:
• Remove the queue’s leading vertex.
• Vertex visited will be noted.
• Add all of the vertex’s unvisited neighbors to the queue.

BFS Complexity

BFS’s time complexity is dependent on the graph representation’s data structure. Since the BFS algorithm searches each node and edge in the worst scenario, its time complexity is O(V+E). The no. of edges in a graph is O(E), while the no. of vertices is O(V).

The number of vertices, V, determines the BFS’s space complexity, which is denoted by the symbol O(V).

Let us see a Java program below to illustrate BFS:

Output

This is BFS Traversal ( and it is starting from vertex 2)

2 0 3 1

Conclusion

In this article, we discussed the breadth-first search technique, as well as its use in the Java programming language, uses, and complexity. We have also demonstrated examples of BFS in use, demonstrating its significance as a data structure algorithm.

Author: Megha Chadha