In Our previous article about Graph, we have seen the different ways to represent the graph.  we have a way to represent this unstructured data structure.  Now question arise is how I will traverse through this given graph structure. 

There are main two methods which we will use to traverse through graph. 

Breadth First Search (BFS) : In breadth first search, we will start from the root node and the visit all the nodes in the next layer.This we repeat until all the nodes are visited in the graph. The assumption we make here is from any node we can reach to any node.

Depth First Search (DFS) : In depth first search, we start from the root node then traverse the graph layerwise until we reach the leaf or dead end. To avoid infinite looping we will mark the visited nodes as visited.

In this article we will see how we can implement BFS. We will cover DFS in next article Graph Search – Depth First Search. 

BFS Implementation:
As the name suggest in BFS,  we first visit all the nodes which are on the same level. Once all the nodes which are on the same level visited then we move to the next level. The same is shown in below image. We will use queue structure to do BFS. We will use BFS to check whether the given graph is directed or not.

We will use adjacency matrix to represent the graph.  We will start from the root node and add it to the queue.

Then we will get the first element of the queue and visit all its adjacent nodes, add them to queue and remove first element from the queue. 

Keep removing the first element from the queue and pushing the next layer nodes to the queue. Also we need to keep marking the visited node, so that we don't get into an infinite loop. We repeat this steps until the queue gets empty.

At the end we will check whether all the nodes get visited or not. If any node is left unvisited then the graph is not connected.

The basic algorithm for BFS can be iterated as below:

set start vertex to visited
load it into queue
while queue not empty
   for each edge incident to vertex
        if its not visited
            load into queue
            mark vertex

The implementation  code snippet will be as below:
 

private boolean bfs(int[][] adjacencyMatrix, int source) {
		int numberOfNodes = adjacencyMatrix.length-1;
		int visited[] = new int[numberOfNodes+1];
		int top =   source;
		visited =1;
		queue.add(source);
		boolean connected = true;
		while(!queue.isEmpty()){
			top = queue.remove();
			if(visited[top] == 0){
				visited[top] = 1;
			}
			for(int i=1; i<numberOfNodes+1;i++){
				if(adjacencyMatrix[top][i] == 1 && visited[i] == 0){
					queue.add(i);
					visited[i] =1;
				}
			}
		}
		
		for(int i=1; i<visited.length;i++){
			if(visited[i] == 0){
				connected = false;
			}
		}
		return connected;
	}

Download Complete Java Program »

The above method will return whether the graph is connected or not. Time complexity for the above implementation will be O(V²). This complexity can be reduced to O(V+E) (V is number of vertices and E is number of edges in the graph) using Adjacency List representation.

Applications:

• Testing whether graph is connected.
• Computing a spanning forest of graph.
• Computing, for every vertex in graph, a path with the minimum number of edges between start vertex and current vertex or reporting that no such path exists.
• Computing a cycle in graph or reporting that no such cycle exists.

Try to implement the same using adjacency list representation.

These algorithms are for searching elements in graph data structure, however we have also written articles on various search  algorithms for array or list like Binary Search and Fibonacci Search.

You will also like to enhance your knowledge by going through our other articles on different algorithms and data structures.