Code Pumpkin

Graph Search – Breadth First Search

April 1, 2017
Posted by Pumpkin
Subscribe

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.

BFS


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;
	}

The above method will return whether the graph is connected or not. Time complexity for the above implementation will be O(V2). 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.

Happy Learning 🙂

Download Complete Java Program »

Tags: , , , , ,


Comments and Queries

If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:
<pre><code class="java"> 
String foo = "bar";
</code></pre>
For more information on supported HTML tags in disqus comment, click here.

Total Post : 80
Subscribe
Contribute Your Articles

Interview Experiences

Related Books

Like Us On Facebook

Alexa Page Rank