Breadth-First Search Algorithm with Java

The Breadth-First search algorithm is a way to traverse through graphs or trees so that the nodes are visited level by level.  The depth-first search algorithm, on the other hand, will traverse nodes to the depth-first as its name suggests, in other words, branch by branch.

The traversal starts from the root node, in the case of the following diagram, from the top. Node 1 will be printed first (level 1), then node 2 and node 3 (level 2), then node 4, node 5, and node 6 (level 3), and finally, node 7 and node 8 (level 4).

As mentioned above, If we traverse the above graph using the breath-first search algorithm we will have the output of:
1 2 3 4 5 6 7 8

Breadth-First Search with a Tree

If you don’t know exactly what is the tree data structure, check out the detailed explanation in the article Tree Data Structure with Java.

Before traversing a tree, let’s see how we define a Binary Tree via code:

public class TreeNode {
  public int value;
  public TreeNode left;
  public TreeNode right;

  public TreeNode(int value) {
    this.value = value;
    right = null;
    left = null;
  }
}

Let’s populate the above tree with the same data from the diagram we’ve seen above in this article:

public class TreeMock {
  public static TreeNode createBfsMock() {
    TreeNode rootTreeNode = new TreeNode(1);
    TreeNode treeNode2 = new TreeNode(2);
    TreeNode treeNode3 = new TreeNode(3);
    TreeNode treeNode4 = new TreeNode(4);
    TreeNode treeNode5 = new TreeNode(5);
    TreeNode treeNode6 = new TreeNode(6);
    TreeNode treeNode7 = new TreeNode(7);
    TreeNode treeNode8 = new TreeNode(8);

    rootTreeNode.left = treeNode2;
    rootTreeNode.right = treeNode3;

    treeNode2.left = treeNode4;
    treeNode2.right = treeNode5;
    treeNode3.right = treeNode6;

    treeNode5.left = treeNode7;
    treeNode5.right = treeNode8;

    return rootTreeNode;
  }
}

In the following algorithm, we will use the data structure queue that uses the FIFO (First-in first out) strategy to insert and retrieve data. In other words, the first element that is in will be the first one that will be out. It’s the same situation as a real-world queue. The first person that is in the queue, will be the first one to be served, or the first one out of the queue.

To use this data structure in Java we will use the Queue interface and the implementation of LinkedList. We will send the root node to the bfsForTree method as a parameter. Then will add the root element to the queue. Finally, we will use a while looping asking if the queue is not empty.

Inside the while looping, we remove the first inserted element by using the poll method. Then, we print the currentNode and add all the adjacent (neighbor) nodes to the queue. The looping goes on until the queue is empty:

import java.util.LinkedList;
import java.util.Queue;

public class BreathFirstSearch {

  public static void main(String[] args) {
    bfsForTree(TreeMock.createBfsMock());
  }

  public static void bfsForTree(TreeNode node) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(node);

    while (!queue.isEmpty()) {
      var currentNode = queue.poll();

      if (currentNode != null) {
        System.out.print(currentNode.value + " ");
        queue.add(currentNode.left);
        queue.add(currentNode.right);
      }
    }
  }

}

Output:
1 2 3 4 5 6 7 8

Breadth-First Search Traversal with Graph

Similarly to traversing a tree, we can also traverse a graph that has cycles. The code doesn’t change too much to traverse a graph.

Now let’s see in code how we describe a Graph and how to populate it as the above diagram in code:

public class Node {

  Object value;
  private List<Node> adjacentNodes = new ArrayList<>();
  private boolean visited;

  public Node(Object value) {
    this.value = value;
  }

  public void addAdjacentNode(Node node) {
    this.adjacentNodes.add(node);
  }

  public Object getValue() {
    visited = true;
    return value;
  }
  // Omitted other methods...
}

Important detail: Notice that in the Node class we have the getValue method that gets a value and also assigns the visited flag with the value of true. That’s because a Node from a Graph can be cyclic and this will be the way we will control if a Node was visited or not in our algorithm.

public class GraphMock {
  
  public static Node createBfsMock() {
    Node rootNode = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    Node node5 = new Node(5);
    Node node6 = new Node(6);
    Node node7 = new Node(7);
    Node node8 = new Node(8);

    rootNode.addAdjacentNode(node2);
    rootNode.addAdjacentNode(node3);
    node2.addAdjacentNode(node4);
    node2.addAdjacentNode(node5);
    node4.addAdjacentNode(node2); // Makes this Graph Mock Cyclic
    node5.addAdjacentNode(node7);
    node5.addAdjacentNode(node8);

    rootNode.addAdjacentNode(node3);
    node3.addAdjacentNode(node6);

    return rootNode;
  }
}

As commented in the code above, we are creating a cyclic Graph. That’s because node2 adds the adjacent node4 and node4 adds the adjacent node2.

Finally, let’s implement the breadth-first search algorithm for a graph. Remember that the main difference between a graph and a tree is that a graph can be cyclic.

Therefore, we need to ask if the node was already visited, if we don’t do that we would get an infinite looping because as mentioned before, the graph we are using is cyclic.

import java.util.ArrayDeque;
import java.util.Queue;

public class BreathFirstSearch {

  public static void main(String[] args) {
    bfsForGraph(GraphMock.createBfsMock());
  }

  public static void bfsForGraph(Node node) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(node);

    while (!queue.isEmpty()) {
      var currentNode = queue.poll();
      if (!currentNode.isVisited()) {
        System.out.print(currentNode.getValue() + " ");
        queue.addAll(currentNode.getAdjacentNodes());
      }
    }
  }

}

Output:
1 2 3 4 5 6 7 8

Breadth-First Search Big(O) Notation

Before checking out the complexity keep in mind that v = vertices and e = edges.

Time Complexity: When we traverse through a Graph, the complexity will be O(v+e) because for every vertice that is inserted into the queue the child nodes will be also inserted. The number of child nodes is exactly the number of edges. Therefore, the time complexity will be O of vertices + edges.

Space Complexity: O(v) because the data inserted into the queue will be exactly the number of vertices from the graph or tree.

Important: To learn more and fully absorb this algorithm, get the code here and run your own tests. 

Summary

– The Breadth-first Search algorithm uses a queue FIFO (First-in First-out) approach.
– The nodes are visited level by level.
– There is no need to check if the node was visited when traversing a tree since a tree can’t be cyclic.
– When we traverse a graph, it’s necessary to check if the node was already visited, otherwise, there will be an infinite loop.