Graph Algorithms: Breadth-First Search (BFS) in Java

Implementation and applications of Breadth-First Search (BFS) algorithm in Java for graph traversal and solving problems like shortest path in unweighted graphs.

⬅ Previous Next ➡

Shortest Path in Unweighted Graphs using BFS (Java)

Introduction

Finding the shortest path between two nodes is a fundamental problem in graph theory. When the graph is unweighted (i.e., all edges have the same weight, typically considered to be 1), Breadth-First Search (BFS) provides an efficient and elegant solution. This document explains the concept, provides a Java code example, and discusses its application in competitive programming.

Shortest Path in Unweighted Graphs using BFS

In an unweighted graph, the shortest path between two nodes is the path with the fewest edges. BFS explores the graph layer by layer, starting from the source node. This characteristic makes it ideal for finding the shortest path because the first time a node is visited during BFS, it's reached via the shortest possible path from the source.

The key idea is that as BFS progresses, the distance from the starting node to any visited node is equal to the number of edges traversed to reach that node. Because BFS explores outwards in a uniform way, any path found to a node will necessarily be the shortest path (in terms of edge count).

Applying BFS to Find the Shortest Path

Here's a breakdown of how to apply BFS to find the shortest path between two nodes in an unweighted graph:

Initialization:
- Create a queue to store nodes to visit.
- Mark the starting node as visited.
- Enqueue the starting node into the queue.
- Initialize a distance array to store the shortest distance from the source node to each node. Set the distance of the source node to 0. For all other nodes, initialize their distance to a large value (e.g., infinity) or -1 if you are using -1 to represent unvisited nodes.
- Initialize a predecessor array to store the parent node of each node in the shortest path. This is needed to reconstruct the actual path later. Initialize it to null or -1 for all nodes.
Iteration:
- While the queue is not empty:
  - Dequeue a node (the current node).
  - For each neighbor of the current node:
    - If the neighbor is not visited:
      - Mark the neighbor as visited.
      - Enqueue the neighbor into the queue.
      - Set the distance of the neighbor to the distance of the current node + 1.
      - Set the predecessor of the neighbor to the current node.
Path Reconstruction (Optional):
- After the BFS is complete, if the destination node has been visited, you can reconstruct the shortest path by backtracking from the destination node to the source node using the predecessor array.

Practical Code Example (Java)

  import java.util.*;

public class ShortestPathBFS {

    public static int[] shortestPath(int n, List<List<Integer>> adj, int startNode, int endNode) {
        int[] dist = new int[n];
        Arrays.fill(dist, -1); // -1 represents unvisited
        int[] parent = new int[n];
        Arrays.fill(parent, -1);

        Queue<Integer> queue = new LinkedList<>();
        dist[startNode] = 0;
        queue.offer(startNode);

        while (!queue.isEmpty()) {
            int u = queue.poll();
            if (u == endNode) break; // Optimization: stop when destination is reached

            for (int v : adj.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    parent[v] = u;
                    queue.offer(v);
                }
            }
        }

        if (dist[endNode] == -1) {
            return new int[0]; // No path exists
        }

        // Reconstruct the path
        List<Integer> pathList = new ArrayList<>();
        int current = endNode;
        while (current != -1) {
            pathList.add(current);
            current = parent[current];
        }
        Collections.reverse(pathList);

        // Convert to array
        int[] path = new int[pathList.size()];
        for (int i = 0; i < pathList.size(); i++) {
            path[i] = pathList.get(i);
        }

        return path;
    }


    public static void main(String[] args) {
        int n = 6; // Number of nodes
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        // Example graph represented as an adjacency list
        adj.get(0).add(1);
        adj.get(0).add(2);
        adj.get(1).add(2);
        adj.get(1).add(3);
        adj.get(2).add(3);
        adj.get(2).add(4);
        adj.get(3).add(5);
        adj.get(4).add(5);

        int startNode = 0;
        int endNode = 5;

        int[] shortestPath = shortestPath(n, adj, startNode, endNode);

        System.out.println("Shortest path from " + startNode + " to " + endNode + ": " + Arrays.toString(shortestPath));
    }
}

Explanation:

The shortestPath function takes the number of nodes (n), an adjacency list (adj), the start node (startNode), and the end node (endNode) as input.
It initializes a dist array to store the shortest distances from the startNode. It uses -1 to denote unvisited nodes.
It initializes a parent array to store the predecessor of each node in the shortest path.
A Queue is used to perform the BFS traversal.
The while loop continues until the queue is empty, processing each node.
For each neighbor of the current node, it checks if the neighbor has been visited. If not, it updates the dist and parent arrays and enqueues the neighbor.
An optimization is included: the BFS loop breaks as soon as the destination node (endNode) is reached. This saves time since we only need the path to that specific node.
After the BFS, the code reconstructs the path by backtracking from the endNode to the startNode using the parent array.
Finally, the function returns the shortest path as an array of node indices. If no path exists, it returns an empty array.
The main function provides an example graph and calls the shortestPath function to find the shortest path between two nodes.

Competitive Programming Considerations

BFS for shortest path is a cornerstone algorithm in competitive programming. Here are some key points:

Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges. This makes it very efficient for sparse graphs.
Space Complexity: O(V), primarily due to the queue and the visited array.
Adjacency List vs. Adjacency Matrix: Using an adjacency list is generally preferred for sparse graphs, as it saves memory and provides better performance. Adjacency matrices are O(V^2) in memory and can be faster for dense graphs where E is close to V^2.
Edge Cases: Always consider edge cases like:
- No path exists between the start and end nodes.
- The start and end nodes are the same.
- Empty graph.
Optimizations: In certain cases, you can optimize the BFS by stopping the search as soon as the target node is found (as shown in the provided code). Also, if you need to find the shortest path from a *single* source to *multiple* destinations, you can run BFS once from the source, storing the distances to all other nodes.

⬅ Previous Next ➡