Learn-dsa..in 30 days!



























CC-4 : Implement Breadth First Search BFS Algorithm.

Description:

BFS search is used for searching elements in graphs or trees. It starts from the root and searches level by level. First the vertexes at the first level from root are searched, then the vertices at second level from root are searched and so on, till the lowest level is reached and searched. Given an input graph and an element to be searched, search the required element in the input graph using BFS search.

Test cases and expected outputs:

Input Parameters Expected outputs
Adjacency list:
vertex 0->4->2->3->1
vertex 1->0->2
vertex 2->0->1->3
vertex 3->0->2->4
vertex 4->0->3 		Bfs search path to : 4 is:
0 4
Adjacency list:
vertex 0->1
vertex 1->0->2->5
vertex 2->1->5->3
vertex 3->2->5->4
vertex 4->5->3
vertex 5->1->2->3->4 		Bfs search path to : 5 is:
0 1 2 5

Pseudocode:

The input vertices and edges of the graph should be converted into adjacency list format (refer chapter on graphs).
Initialize an integer array named visited to store information whether a particular vertex has been visited(processed).
Initialize a String variable named bfsTraversal to hold output of DFS traversal of the graph from root to the vertex to be searched.

Method bfsSearch(currVertex, toSearch):

Set visited[vertex] to 1, as the current vertex has been processed.
Instantiate a variable of type LinkedList named queue to hold a list of nodes to be processed.
Add vertex to queue.
While queue size is not 0:
Extract first element from queue and store it in a variable named vertex.
Append vertex to variable bfsTraversal as current vertex has been processed now.
If currVertex==toSearch, return true from the method as we have found the vertex to be searched. We can check the value of dfsTraversal String as it contains the path of the required vertex from the root.
Iterate through vertices connected to current vertex using iterator:
Set variable adjacentNode to point to current connected vertex in the iterator.
If visited[adjacentNode] is not 1, then:
Set visited[adjacentNode] to 1.
Add adjacentNode to the queue.
If required vertex is not found in the above search, return false.

Code:

public class SearchGraphBfs {

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 String bfsTraversal=new String();
 
 public SearchGraphBfs(int vertices) {
	 this.vertices=vertices;
	 visited=new int[vertices];
	 for (int iIdx=0; iIdx < vertices; iIdx++) {
		 adjacencyLists.add(new ArrayList<Integer>());
		 visited[iIdx]=0;
	 }
 }
 
 public void addEdge(int source, int dest) {
	 adjacencyLists.get(source).add(dest);
	 adjacencyLists.get(dest).add(source);
 }
 
 public boolean bfsSearch(int vertex,int toSearch) {
	 visited[vertex]=1;
	 LinkedList<Integer> queue=new LinkedList<Integer>();
	 queue.add(vertex);
	 while (queue.size() !=0) {
		 vertex=queue.remove();
		 bfsTraversal+= vertex + " ";
		 if (vertex==toSearch) {
			 return true;
		 }
		 Iterator<Integer> itr=adjacencyLists.get(vertex).iterator();
		 while (itr.hasNext()) {
		 int adjacentNode=itr.next();
		 if (visited[adjacentNode]==0) {
			 visited[adjacentNode]=1;
			 queue.add(adjacentNode);			
		 }
		 }
	 }
	return false;	
 }
 }

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us