Here you will get Breadth First Search (BFS) Java program along with example.
Breadth First Search is graph traversal algorithm which has many applications in most of the algorithms. We will start with one node and we will explore all the nodes (neighbor nodes) in the same level. Then we should go to next level to explore all nodes in that level. Here BFS should fallow the graph traversal rule that it should visit each node exactly once.
Also Read: Depth First Search (DFS) Java Program
BFS uses Queue data structure to impose rule on traversing that first discovered node should be explored first.
Trees won’t have cycles. So no need to keep track of visited nodes. But in case of graph cycles will present. We may visit already visited node so we should keep track of visited node.
Breadth First Search (BFS) Example
Here we are having a graph with 6 vertices.
Now we will see how BFS will explore the vertices.
Step1: start with one node of graph. Add that node to the queue.
Step2: Remove the node from queue and add the children to the queue. Here C, E are the children of A. Add elements C, E to the queue. Now A is explored but E, C are just discovered.
Step 3: In queue next element is C. We should explore C first. Now remove C from queue and add it’s children to the queue.
Step 4: Now C is explored. Next element in queue is E. Add E children to queue and remove E from queue.
Step 5: Next node in queue is B. No children are there so it will print the element and B will be removed from queue.
Step 6: next element in queue is D. As D doesn’t have any children it will print D and D will be removed form queue.
Step 7: Next element in queue is F. It doesn’t have any children so it will print and removed form queue.
This way we should explore all vertices in BFS.
If in case of disconnected graph we should keep track of unvisited nodes so that we can call again BFS on that node.
Now we see the program for breadth first search in Java which will work on disconnected components also.
Breadth First Search (BFS) Java Program
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
import java.util.*; import java.util.Queue; public class BFS{ private int n; private LinkedList<Integer> adjList[]; private Queue<Integer> q = new LinkedList(); // creating adjacency list for each vertex. public void makeGraph(int no) { n = no; adjList = new LinkedList[no]; int i; for (i= 0; i < no; i++) { adjList[i] = new LinkedList(); } } // adding edges to graph public void addEdgeToGraph(int u, int v) { adjList[u].add(v); } //BFtravesal function traverse one connected component of graph public void BFtraversal(int v, boolean[] visited) { q.add(v); visited[v] = true; int k; while( !q.isEmpty() ) { k = q.remove(); System.out.print( k +" "); // we are iterating through adjacency list of vertex k which has to be explored now. // it will give the adjacent nodes of each vertex. Iterator<Integer> i = adjList[k].listIterator(); int j; while( i.hasNext() ) { j = i.next(); if( visited[j] != true ) { // if any child found with out visiting then those child will be added to queue. q.add(j); visited[j] = true; } } } } // BFsearch function will maintain boolean array to know which vertex is explored. // If in case of disconnected graph it will again call BFtravesal on another component public void BFsearch(int v) { boolean visited[] = new boolean[n]; BFtraversal(v, visited); for ( int i = 0; i < n; i++ ) { // after calling BFtraveral it is checking whether any vertex left out with out exploring if( visited[i] != true ) { // if found it will call again BFtraversal BFtraversal(i, visited); } } } public static void main(String args[]) { BFS obj = new BFS(); //make graph will make 10 vertices and it will maintain an adjacency list for each vertex. obj.makeGraph(10); obj.addEdgeToGraph(0, 1); obj.addEdgeToGraph(0, 9); obj.addEdgeToGraph(2, 3); obj.addEdgeToGraph(2, 4); obj.addEdgeToGraph(3, 5); obj.addEdgeToGraph(3, 6); obj.addEdgeToGraph(4, 7); obj.addEdgeToGraph(4, 8); System.out.println("BFS of graph is:"); // we are starting search from 0th vertex. obj.BFsearch(0); } } |
Output
BFS of graph is:
0 1 9 2 3 4 5 6 7 8
Applications of Breadth First Search
- Finding minimum spanning tree.
- Shortest path finding.
- In networks BFS will be used for finding all neighboring nodes.
- In Navigation systems BFS will be useful for finding neighboring locations.
- Parsing social networking graphs.
- In garbage collection also BFS will be useful.
- To find connected components we can use BFS also.
- For crawling the search engines also it will be useful.
Comment below if you have queries or found any information incorrect in above breadth first search Java program.
