BFS Algorithm in Java

The Breadth-First Search (BFS) algorithm is one of the most commonly used algorithms for traversing or searching tree or graph data structures. It explores all the vertices of a graph in breadthward motion, visiting all nodes at the present depth level before moving on to nodes at the next depth level. BFS is particularly useful when finding the shortest path in an unweighted graph, as it ensures the shortest path is found by examining nodes in increasing distance from the source.

In this blog post, we will dive into the BFS algorithm in Java, explaining its concept, how it works, and how you can implement it in your Java programs.

What is BFS (Breadth-First Search)?

BFS is a graph traversal algorithm used to explore nodes in a graph systematically. Unlike Depth-First Search (DFS), which goes as deep as possible along each branch before backtracking, BFS explores all the neighbors of a node before moving on to the next level.

Key Characteristics of BFS:

• BFS starts at a selected node (often called the source or root) and explores all its neighbors before moving on to their neighbors.
• BFS explores nodes level by level, which makes it ideal for finding the shortest path in an unweighted graph.
• BFS uses a queue data structure to keep track of the nodes to be visited, ensuring that nodes are explored in the correct order.

How Does BFS Work?

Here’s a high-level step-by-step process of how the BFS algorithm works:

1. Initialize: Start by adding the source node to a queue.
2. Explore: While the queue is not empty, do the following:
   • Remove a node from the front of the queue.
   • If the node has not been visited yet, mark it as visited and perform any necessary action (e.g., print the node, process data, etc.).
   • Add all the unvisited neighbors of the current node to the queue.
3. Repeat: Continue the process until all reachable nodes have been visited.

This ensures that the algorithm explores all nodes at a given level before moving to the next level.

BFS Algorithm in Java

To implement BFS in Java, we typically use a queue to manage the nodes that need to be visited. A queue is perfect for BFS because it follows the First In, First Out (FIFO) principle, which ensures nodes are visited level by level.

Let’s implement a simple BFS algorithm for an unweighted graph using Java.

Java Implementation of BFS

In this example, we will implement a BFS algorithm for a graph represented as an adjacency list.

Step 1: Create the Graph

We will represent the graph using an adjacency list, where each node points to a list of its neighbors.

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adjList;

    public Graph() {
        adjList = new HashMap<>();
    }

    // Add an edge to the graph
    public void addEdge(int v, int w) {
        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(w);
    }

    // Perform BFS traversal
    public void bfs(int startNode) {
        // Create a queue for BFS
        Queue<Integer> queue = new LinkedList<>();
        // Set to keep track of visited nodes
        Set<Integer> visited = new HashSet<>();
        
        // Start with the starting node
        visited.add(startNode);
        queue.offer(startNode);
        
        while (!queue.isEmpty()) {
            // Dequeue a vertex from the queue
            int node = queue.poll();
            System.out.print(node + " ");
            
            // Get all adjacent nodes
            for (int neighbor : adjList.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    // If the neighbor hasn't been visited, mark it and add it to the queue
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }
}

Step 2: Test the BFS Implementation

Now, let’s create a Graph object, add some edges to it, and perform a BFS traversal.

public class BFSExample {
    public static void main(String[] args) {
        // Create the graph
        Graph graph = new Graph();
        
        // Add edges to the graph
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(2, 5);
        graph.addEdge(3, 6);
        
        // Perform BFS starting from node 1
        System.out.println("BFS Traversal starting from node 1:");
        graph.bfs(1);
    }
}

Output:

BFS Traversal starting from node 1:
1 2 3 4 5 6

In this example:

• The graph has six nodes, and the edges are added using the addEdge method.
• The BFS traversal starts from node 1 and visits the nodes level by level: 1 -> 2 -> 3 -> 4 -> 5 -> 6.

BFS in a Directed Graph

The BFS implementation provided works for both directed and undirected graphs. However, for directed graphs, the edges only go in one direction, so BFS will explore the nodes in accordance with the direction of the edges.

Applications of BFS

BFS has several important applications in computer science and is widely used in a variety of fields. Some of the key applications include:

1. Finding the Shortest Path: BFS is optimal for finding the shortest path in an unweighted graph because it explores nodes level by level. The first time a node is reached, it is guaranteed to be reached by the shortest path.
2. Web Crawling: Search engines use BFS to crawl websites. The algorithm explores all pages linked from a starting page, then explores all the pages linked from those, and so on.
3. Social Networks: BFS is used to find the degree of separation between people in a social network. It can also help identify connected components within a network.
4. Puzzle Solving: In many puzzle-based games (e.g., maze solvers), BFS can be used to find the shortest sequence of moves from a start point to the goal.
5. Peer-to-Peer Networks: BFS is used to find the shortest route for data to travel between nodes in peer-to-peer (P2P) networks.

Time Complexity of BFS

The time complexity of BFS is O(V + E), where:

• V is the number of vertices (nodes) in the graph.
• E is the number of edges in the graph.

This complexity arises because BFS explores each node and edge at most once. The V accounts for the number of nodes to be visited, and the E accounts for the edges traversed during the process.

Conclusion

The BFS algorithm is a powerful graph traversal technique that allows you to explore a graph level by level. It is particularly useful for finding the shortest path in an unweighted graph and solving problems involving connectivity and search in graphs.

In this post, we explored:

• What BFS is and how it works.
• The Java implementation of BFS using a queue.
• Applications of BFS, including shortest path finding and web crawling.
• The time complexity of BFS.

By understanding BFS and its implementation in Java, you can apply it to a wide range of problems in computer science, making it an essential tool in your algorithmic toolbox.