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);
}