# Graph Search – Breadth First Search

April 1, 2017

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
while queue not empty
for each edge incident to vertex
if its not visited
mark vertex``````

The implementation  code snippet will be as below:

```private boolean bfs(int[][] adjacencyMatrix, int source) {
int visited[] = new int[numberOfNodes+1];
int top =   source;
visited =1;
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){
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.

That's all for this topic. If you guys have any suggestions or queries, feel free to drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here.

Happy Learning 🙂

If you like the content on CodePumpkin and if you wish to do something for the community and the planet Earth, you can donate to our campaign for planting more trees at CodePumpkin Cauvery Calling Campaign.

We may not get time to plant a tree, but we can definitely donate ₹42 per Tree. Coder, Blogger, Wanderer, Philosopher, Curious pumpkin

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>
```