Implementing BFS in Java | Breadth First Search Algorithm

Graph traversal is the process of moving from the root node to all other nodes in the graph. The order of nodes given by a traversal will vary depending upon the algorithm used for the process. As such, graph traversal is done using two main algorithms: Breadth-First Search and Depth-First Search. In this article, we are going to go over the basics of one of the traversals, breadth first search in java, understand BFS algorithm with example and BFS implementation with java code. Also, If you are stuck anywhere with your java programming, our experts will be happy to provide you with any type of Java homework help.

What is a Breadth-First Search?

Breadth-First Search (BFS) relies on the traversal of nodes by the addition of the neighbor of every node starting from the root node to the traversal queue. BFS for a graph is similar to a tree, the only difference being graphs might contain cycles. Unlike depth-first search, all of the neighbor nodes at a certain depth are explored before moving on to the next level.

BFS Algorithm

The general process of exploring a graph using breadth-first search includes the following steps:-

• Take the input for the adjacency matrix or adjacency list for the graph.
• Initialize a queue.
• Enqueue the root node (in other words, put the root node into the beginning of the queue).
• Dequeue the head (or first element) of the queue, then enqueue all of its neighboring nodes, starting from left to right. If a node has no neighboring nodes which need to be explored, simply dequeue the head and continue the process. (Note: If a neighbor which is already explored or in the queue appears, don’t enqueue it – simply skip it.)
• Keep repeating this process till the queue is empty.

(In case people are not familiar with enqueue and dequeue operations, enqueue operation adds an element to the end of the queue while dequeue operation deletes the element at the start of the queue.)

Example

Let’s work with a small example to get started. We are using the graph drawn below, starting with 0 as the root node.

Iteration 1: Enqueue(0).

Queue after iteration 1 :

Iteration 2: Dequeue(0), Enqueue(1), Enqueue(3), Enqueue(4).

Queue after iteration 2:

Iteration 3: Dequeue(1), Enqueue(2).

Queue after iteration 3 :

Iteration 4 : Dequeue(3), Enqueue(5). Since 0 is already explored, we are not going to add 1 to the queue again.

Queue after iteration 4:

Iteration 5: Dequeue(4).

Queue after iteration 5:

Iteration 6: Dequeue(2).

Queue after iteration 6 :

Iteration 7: Dequeue(5).

Queue after iteration 7:

Since the queue is again empty at this point, we will stop the process.

Edge Cases

Now, there’s always the risk that the graph being explored has one or more cycles. This means that there’s a chance of getting back to a node that we have already explored. How do we determine if a node has been explored or not? It’s simple – we simply maintain an array for all the nodes. The array at the beginning of the process will have all of its elements initialized to 0 (or false). Once a node is explored once, the corresponding element in the array will be set to 1 (or true). We simply enqueue nodes if the value of their corresponding element in the array is 0 (or false).

That’s cool, but there’s still another case to consider while you’re traversing all the nodes of a graph using the BFS in java. What happens when the graph being provided as input is a disconnected graph? In other words, what happens when the graph has not one, but multiple components which are not connected? It’s simple. As described above, we will maintain an array for all of the elements in the graph. The idea is to iteratively perform the BFS algorithm for every element of the array which is not set to 1 after the initial run of the BFS algorithm is completed. This is even more relevant in the case of directed graphs because of the addition of the concept of “direction” of traversal.

Applications

Breadth-First Search has a lot of utility in the real world because of the flexibility of the algorithm. These include:-

• Discovery of peer nodes in a peer-to-peer network. Most torrent clients like BitTorrent, uTorrent, qBittorent use this mechanism for discovering something called “seeds” and “peers” in the network.
• Web crawling uses graph traversal techniques for building the index. The process considers the source page as the root node and starts traversing from there to all secondary pages linked with the source page (and this process continues). Breadth-First Search has an innate advantage here because of the reduced depth of the recursion tree.
• GPS navigation systems use Breadth-First Search for finding neighboring locations using the GPS.
• Garbage collection is done with Cheney’s algorithm which utilizes the concept of breadth-first search.

Algorithms for finding minimum spanning tree and shortest path in a graph using Breadth-first search.

Implementing Breadth-First Search in Java

There are multiple ways of dealing with the code. Here, we would primarily be sharing the process for a breadth first search implementation in java. Graphs can be stored either using an adjacency list or an adjacency matrix – either one is fine. In our code, we will be using the adjacency list for representing our graph. It is much easier to work with the adjacency list for implementing the Breadth-First Search algorithm in Java as we just have to move through the list of nodes attached to each node whenever the node is dequeued from the head (or start) of the queue.

The graph used for the demonstration of the code will be the same as the one used for the above example.

The implementation is as follows:-

import java.io.*;
import java.util.*;

class Graph
{
    private int V;                              //number of nodes in the graph
    private LinkedList<Integer> adj[];              //adjacency list
    private Queue<Integer> queue;                   //maintaining a queue
 
    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; i++)
        {
            adj[i] = new LinkedList<>();
        }
        queue = new LinkedList<Integer>();
    }

 
    void addEdge(int v,int w)
    {
        adj[v].add(w);                          //adding an edge to the adjacency list (edges are bidirectional in this example)
    }
 
    void BFS(int n)
    {

        boolean nodes[] = new boolean[V];       //initialize boolean array for holding the data
        int a = 0;
 
        nodes[n]=true;                  
        queue.add(n);                   //root node is added to the top of the queue
 
        while (queue.size() != 0)
        {
            n = queue.poll();             //remove the top element of the queue
            System.out.print(n+" ");           //print the top element of the queue
 
            for (int i = 0; i < adj[n].size(); i++)  //iterate through the linked list and push all neighbors into queue
            {
                a = adj[n].get(i);
                if (!nodes[a])                    //only insert nodes into queue if they have not been explored already
                {
                    nodes[a] = true;
                    queue.add(a);
                }
            }  
        }
    }

    public static void main(String args[])
    {
        Graph graph = new Graph(6);
 
        graph.addEdge(0, 1);
        graph.addEdge(0, 3);
        graph.addEdge(0, 4);
        graph.addEdge(4, 5);
        graph.addEdge(3, 5);
        graph.addEdge(1, 2);
        graph.addEdge(1, 0);
        graph.addEdge(2, 1);
        graph.addEdge(4, 1);
        graph.addEdge(3, 1);
        graph.addEdge(5, 4);
        graph.addEdge(5, 3);
 
        System.out.println("The Breadth First Traversal of the graph is as follows :");
 
        graph.BFS(0);
    }
}

Output

Time & Space Complexity

The running time complexity of the BFS in Java is O(V+E) where V is the number of nodes in the graph, and E is the number of edges.

Since the algorithm requires a queue for storing the nodes that need to be traversed at any point in time, the space complexity is O(V).

Conclusion

Graph traversal algorithms are some of the most important algorithms that one has to master to get into graphs. Breadth first search in java is one of the things one needs to learn before one can proceed to stuff like finding the minimum spanning tree and shortest path between two nodes in a graph. This article on the implementation of the BFS algorithm in java should help bring your concepts up to scratch. You can also check how to implement depth first search in java to complete the concept of graph traversal.