Hello everyone Thank you for visiting my blog. In it, we explore the fascinating world of a unique algorithm known as the Breadth-First Search Algorithm. My name is Sourasis Mukherjee. The breadth-first search graph traversal algorithm examines each node in the graph beginning with the root node. Then it selects the nearest node and explores each undiscovered node. When using the BFS for traversal, any node in the graph might act as the root node.
Although there are alternative methods for navigating the graph, BFS is the one that is most usually used. In a tree or graph data structure, the process of searching each vertex is recursive. BFS divides each vertex in the graph into two categories: visited and non-visited. In a graph, one node is selected, and all of the nodes that are adjacent to that node are subsequently visited.
Applications of the BFS algorithm
The applications of the breadth-first-algorithm are –
- From a given specific source location, BFS can be used to locate nearby places.
- Web crawlers can use BFS to build indexes for web pages. Every web page is viewed in this case as a node in the graph.
- The shortest path and least spanning tree are found using BFS.
Code
import java.io.*;
import java.util.*;
public class BFSTraversal
{
private int vertex; /* total number number of vertices in the graph */
private LinkedList<Integer> adj[]; /* adjacency list */
private Queue<Integer> que; /* maintaining a queue */
BFSTraversal(int v)
{
vertex = v;
adj = new LinkedList[vertex];
for (int i=0; i<v; i++)
{
adj[i] = new LinkedList<>();
}
que = new LinkedList<Integer>();
}
void insertEdge(int v,int w)
{
adj[v].add(w); /* adding an edge to the adjacency list (edges are bidirectional in this example) */
}
void BFS(int n)
{
boolean nodes[] = new boolean[vertex]; /* initialize boolean array for holding the data */
int a = 0;
nodes[n]=true;
que.add(n); /* root node is added to the top of the queue */
while (que.size() != 0)
{
n = que.poll(); /* remove the top element of the queue */
System.out.print(n+” “); /* print the top element of the queue */
for (int i = 0; i < adj[n].size(); i++) /* iterate through the linked list and push all neighbors into queue */
{
a = adj[n].get(i);
if (!nodes[a]) /* only insert nodes into queue if they have not been explored already */
{
nodes[a] = true;
que.add(a);
}
}
}
}
public static void main(String args[])
{
BFSTraversal graph = new BFSTraversal(10);
graph.insertEdge(0, 1);
graph.insertEdge(0, 2);
graph.insertEdge(0, 3);
graph.insertEdge(1, 3);
graph.insertEdge(2, 4);
graph.insertEdge(3, 5);
graph.insertEdge(3, 6);
graph.insertEdge(4, 7);
graph.insertEdge(4, 5);
graph.insertEdge(5, 2);
graph.insertEdge(6, 5);
graph.insertEdge(7, 5);
graph.insertEdge(7, 8);
System.out.println(“Breadth First Traversal for the graph is:”);
graph.BFS(2);
}
}
Output
Conclusion
In this post, we covered the breadth-first search technique, as well as its use in the Java programming language, difficulty, and example. Here, we have also seen examples of BFS in use, demonstrating its significance as a data structure algorithm.
That concludes the article. I hope it will be instructive and useful to you.
AUTHOR-SOURASIS MUKHERJEE
Disclaimer: The author(s) of this blog are solely responsible for the content posted. The blog platform serves as a medium for their expression, and the platform administrators assume no liability for the accuracy or legality of the content.
