Graph Breadth First Search in Java, easy in 5 minutes

The post shows you Graph Breadth First Search in Java. Breadth First Search or Breadth First Traversal is a recursive algorithm for visiting all the vertices of a graph or tree data structure. There is different a bit between searching for a graph and a tree. Let’s dive into it.

Graph Breadth First Search in Java

Breadth First Search (BFS) Algorithm

When visiting a graph from a vertex to another vertex, you maybe get loops so a vertex might be visited again. Here, we can fix it by using a flag of boolean type to mark a visited vertex. For simplicity, it is assumed that all vertices are reachable from the starting vertex and we put vertices that need to visit into a queue.

Graph Breadth First Search in Java

The Breadth First Search Algorithm works as follows:

  1. Putting a vertex of the graph at the back of a queue.
  2. Pop the front item of the queue and mark it as visited.
  3. Create a list of that vertex’s adjacent nodes. Then just add the ones which aren’t visited into the back of the queue.
  4. Keep repeating steps 2 and 3 until the queue is empty.
Breadth First Search Algorithm pseudocode

Time and space complexity

The time complexity can be expressed as O(V + E), V is the number of vertices and E is the number of edges in the graph since every vertex and every edge will be explored in the worst case.

The space complexity can be expressed as O(V).

Implement of BFS

Now, you can implement a Graph Breadth First Search in Java looks like this program

Here is output

 

That’s all about Graph Breadth First Search in Java.

References

Graph Data Structure in Java


Graph documentation

Please share it if you found this useful
Hide Buttons