Breadth First Search (BFS) in Java

Yasin Cakal

Breadth First Search (BFS) is an algorithm used for traversing and searching a graph or tree data structure. It is a widely used algorithm in computer science, and it is one of the most basic algorithms used to traverse a graph. BFS is used to find the shortest paths between two nodes in a graph, and it is also used to find connected components in an undirected graph. This article will cover the fundamentals of Breadth First Search (BFS), how the algorithm works, its time complexity, and its space complexity.

Understanding Graphs

Before diving into Breadth First Search (BFS), it is important to understand what a graph is. A graph is a data structure consisting of nodes (or vertices) and edges. Nodes represent the objects in the graph, and edges represent the connections between these objects. Graphs can be undirected or directed. In an undirected graph, the edges between nodes do not have a direction, and the edges in a directed graph are directed from one node to another.

How Breadth First Search (BFS) Works

Breadth First Search (BFS) is an algorithm used for traversing and searching a graph or tree data structure. BFS works by traversing the graph in layers. It starts at the root node and explores each of the immediate neighbor nodes at the current layer before moving on to the next layer. This process is repeated until the desired node is found or all the nodes in the graph have been visited.

The algorithm begins by putting the root node in a queue and examining the neighbors of the root node. The neighbors of the root node are then added to the queue and visited in the same order they were added. As the algorithm continues, each node is visited in the order it was added to the queue. The algorithm continues until the desired node is found or all the nodes in the graph have been visited.

Time Complexity

The time complexity of Breadth First Search (BFS) is dependent on the size of the graph. The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This means that the time complexity of BFS is linear, as the number of vertices and edges increase, the time complexity will also increase linearly.

Space Complexity

The space complexity of Breadth First Search (BFS) is also dependent on the size of the graph. The space complexity of BFS is O(V), where V is the number of vertices in the graph. This means that the space complexity of BFS is proportional to the number of vertices in the graph.

Example in Java

Now that we have an understanding of how Breadth First Search (BFS) works and its time and space complexity, we will look at an example of how to implement BFS in Java.

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

public class BFS {
  
  // Initialize a queue
  Queue<Node> queue = new LinkedList<Node>();

  // Add the root node to the queue
  queue.add(root);

  // While the queue is not empty
  while(!queue.isEmpty()) {
      // Get the first node from the queue
      Node node = queue.poll();

      // Visit the node
      visit(node);

      // Add the node's children to the queue
      for(Node child : node.getChildren()) {
          queue.add(child);
      }
  }
}

Conclusion

In conclusion, Breadth First Search (BFS) is an algorithm used for traversing and searching a graph or tree data structure. It is a widely used algorithm in computer science, and it is one of the most basic algorithms used to traverse a graph. The time complexity of BFS is O(V + E) and the space complexity is O(V), where V is the number of vertices and E is the number of edges in the graph. We have also looked at an example of how to implement BFS in Java.

Exercises

Write a Java program to implement Breadth First Search (BFS) to traverse a graph.

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

public class BFS { 
  // Initialize a queue 
  Queue<Node> queue = new LinkedList<Node>(); 

  // Add the root node to the queue 
  queue.add(root); 

  // While the queue is not empty 
  while(!queue.isEmpty()) { 
      // Get the first node from the queue 
      Node node = queue.poll(); 

      // Visit the node 
      visit(node); 

      // Add the node's children to the queue 
      for(Node child : node.getChildren()) { 
          queue.add(child); 
      } 
  } 
}

Write a Java program to find the shortest path between two nodes in a graph using Breadth First Search (BFS).

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

public class BFS { 
  // Initialize a queue 
  Queue<Node> queue = new LinkedList<Node>(); 

  // Add the root node to the queue 
  queue.add(root); 

  // Create a list to store the shortest path 
  List<Node> shortestPath = new ArrayList<>(); 

  // While the queue is not empty 
  while(!queue.isEmpty()) { 
      // Get the first node from the queue 
      Node node = queue.poll(); 

      // If the node is the destination node, add it to the shortest path 
      if(node.getValue().equals(destination)) { 
          shortestPath.add(node); 
          break; 
      } 

      // Visit the node 
      visit(node); 

      // Add the node's children to the queue 
      for(Node child : node.getChildren()) { 
          queue.add(child); 
      } 
  } 

  // Print the shortest path 
  for(Node node : shortestPath) { 
      System.out.println(node.getValue()); 
  } 
}

Write a Java program to find the connected components in an undirected graph using Breadth First Search (BFS).

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

public class BFS { 
  // Initialize a queue 
  Queue<Node> queue = new LinkedList<Node>(); 

  // Add the root node to the queue 
  queue.add(root); 

  // Create a list to store the connected components 
  List<List<Node>> components = new ArrayList<>(); 

  // While the queue is not empty 
  while(!queue.isEmpty()) { 
      // Create a list to store the connected component 
      List<Node> component = new ArrayList<>(); 

      // Get the first node from the queue 
      Node node = queue.poll(); 

      // Add the node to the connected component 
      component.add(node); 

      // Visit the node 
      visit(node); 

      // Add the node's children to the queue 
      for(Node child : node.getChildren()) { 
          queue.add(child); 
      } 

      // Add the connected component to the list of components 
      components.add(component); 
  } 

  // Print the connected components 
  for(List<Node> component : components) { 
      for(Node node : component) { 
          System.out.println(node.getValue()); 
      } 
  } 
}

Write a Java program to find the number of nodes in a graph using Breadth First Search (BFS).

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

public class BFS { 
  // Initialize a queue 
  Queue<Node> queue = new LinkedList<Node>(); 

  // Add the root node to the queue 
  queue.add(root); 

  // Initialize a counter to keep track of the number of nodes 
  int count = 0; 

  // While the queue is not empty 
  while(!queue.isEmpty()) { 
      // Get the first node from the queue 
      Node node = queue.poll(); 

      // Increment the counter 
      count++; 

      // Visit the node 
      visit(node); 

      // Add the node's children to the queue 
      for(Node child : node.getChildren()) { 
          queue.add(child); 
      } 
  } 

  // Print the number of nodes 
  System.out.println("Number of nodes: " + count); 
}

Write a Java program to find the diameter of a graph using Breadth First Search (BFS).

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

public class BFS { 
  // Initialize a queue 
  Queue<Node> queue = new LinkedList<Node>(); 

  // Add the root node to the queue 
  queue.add(root); 

  // Create a list to store the visited nodes 
  List<Node> visited = new ArrayList<>(); 

  // Initialize a maximum distance 
  int maxDistance = 0; 

  // While the queue is not empty 
  while(!queue.isEmpty()) { 
      // Get the first node from the queue 
      Node node = queue.poll(); 

      // Visit the node 
      visit(node); 

      // Add the node's children to the queue 
      for(Node child : node.getChildren()) { 
          queue.add(child); 

          // Calculate the distance between the node and the child 
          int distance = calculateDistance(node, child); 

          // Update the maximum distance 
          if(distance > maxDistance) { 
              maxDistance = distance; 
          } 
      } 
  } 

  // Print the diameter of the graph 
  System.out.println("Diameter of the graph: " + maxDistance); 
}

Data Structures and Algorithms with Java

Participants 673