BFS for Shortest Path in Unweighted Graphs

1. The Core Idea of BFS: Exploring Level by Level

Imagine dropping a stone into a still pond. The ripples expand outwards in concentric circles, reaching all points at a certain distance at the same time before moving to the next "level." BFS explores a graph in the exact same way.

Starting from a source node, BFS:

1. Visits the source node itself.
2. Visits all of its direct neighbors (level 1).
3. Visits all of their unvisited neighbors (level 2).
4. And so on, exploring the graph layer by layer.

This "level-by-level" traversal is the reason BFS is guaranteed to find the shortest path in an unweighted graph. The first time it reaches any node, it has done so via the minimum number of edges.

To manage this exploration, BFS relies on two key data structures:

• A Queue to store the nodes to visit next. Its First-In, First-Out (FIFO) nature ensures we process nodes in the order they were discovered, maintaining the level-by-level traversal.
• A visited array or set to keep track of nodes we've already seen, preventing us from getting stuck in infinite loops in graphs with cycles.

To see this process in action, the following animation provides a clear visual.

2. From Traversal to Shortest Path

Now, how do we adapt this traversal to calculate the shortest distance from a source node to all other nodes? Instead of just a boolean visited array, we'll use an integer array to store distances.

The algorithm is a clever modification of the standard BFS:

1. Create a distance array of size V (number of vertices) and initialize all its values to a large number (representing infinity).
2. Create a queue and add the source node to it.
3. Set distance[source] = 0.
4. While the queue is not empty:
   • Dequeue a node, let's call it u.
   • For each neighbor v of u:
     • If v has not been visited yet (i.e., distance[v] is still infinity), it means we've found the shortest path to it.
     • Update its distance: distance[v] = distance[u] + 1.
     • Enqueue v to be processed later.

This works because BFS ensures that when we process node u, we have already found the shortest path to it. Therefore, the shortest path to its unvisited neighbor v must be exactly one edge longer.

The following video provides an excellent, detailed walkthrough of this exact process.

3. Java Implementation

Now, let's translate this algorithm into Java code. We'll write a function that takes the number of vertices, the adjacency list (which you learned to build in the last lesson), and the source vertex as input. It will return an array containing the shortest distances.

The take U forward video you just watched also provides a clean Java implementation. Let's review it and then present a complete, runnable example.

Here is a full Java program that implements the shortest path algorithm using BFS. You can run this code to test it.

import java.util.*;

public class ShortestPathBFS {

    public static int[] findShortestPath(int n, ArrayList<ArrayList<Integer>> adj, int src) {
        // 1. Initialize distance array with a large value (infinity)
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);

        // 2. Create a queue for BFS
        Queue<Integer> q = new LinkedList<>();

        // 3. Set distance of source to 0 and add to queue
        dist[src] = 0;
        q.add(src);

        // 4. Main BFS loop
        while (!q.isEmpty()) {
            int node = q.poll(); // Dequeue the current node

            // Iterate through all its neighbors
            for (int neighbor : adj.get(node)) {
                // If we found a shorter path (i.e., this neighbor hasn't been visited)
                if (dist[node] + 1 < dist[neighbor]) {
                    dist[neighbor] = dist[node] + 1;
                    q.add(neighbor); // Enqueue the neighbor for future processing
                }
            }
        }

        // Optional: Replace MAX_VALUE with -1 for unreachable nodes for cleaner output
        for (int i = 0; i < n; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                dist[i] = -1;
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        // Using the graph from the 'take U forward' video
        int n = 9; // 9 vertices, 0-indexed
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        // Edges for the undirected graph
        // (u, v) -> add edge from u to v and v to u
        addEdge(adj, 0, 1);
        addEdge(adj, 0, 3);
        addEdge(adj, 1, 2);
        addEdge(adj, 1, 3);
        addEdge(adj, 2, 6);
        addEdge(adj, 3, 4);
        addEdge(adj, 4, 5);
        addEdge(adj, 5, 6);
        addEdge(adj, 6, 7);
        addEdge(adj, 6, 8);
        addEdge(adj, 7, 8);
        
        int source = 0;
        int[] shortestDistances = findShortestPath(n, adj, source);

        System.out.println("Shortest distances from source node " + source + ":");
        System.out.println(Arrays.toString(shortestDistances)); 
        // Expected output: [0, 1, 2, 1, 2, 3, 3, 4, 4]
    }

    private static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }
}

Complexity Analysis

• Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. Each vertex is enqueued and dequeued exactly once (O(V)). When we process a vertex, we iterate through its adjacency list. Over the entire algorithm, each edge is considered exactly twice (once from each direction in an undirected graph), leading to O(E).
• Space Complexity: O(V). In the worst case (a star graph or a complete graph), the queue can hold up to V-1 vertices. The distance array also requires O(V) space.

4. Reconstructing the Actual Path

The function above finds the length of the shortest path. But what if an interview question asks you to return the sequence of nodes in the path?

To do this, we need one more piece of information: a parent array.

The logic is simple:

1. Initialize a parent array.
2. When you update the distance to a neighbor v from node u (dist[v] = dist[u] + 1), you also record its parent: parent[v] = u.
3. Once the BFS is complete, to find the path to a destination t, you start at t and repeatedly move to parent[t] until you reach the source. This gives you the path in reverse, which you can then easily correct.

This is a common follow-up and an important extension of the base algorithm.

Conclusion

Congratulations! You've successfully implemented one of the most important graph algorithms. It's a cornerstone of solving many problems related to connectivity and pathfinding.

Key Takeaways:

• BFS explores a graph in a level-by-level fashion using a queue.
• This property makes BFS the ideal algorithm for finding the shortest path in an unweighted graph.
• The implementation requires a queue to manage the traversal and a distance array (initialized to infinity) to store the shortest path lengths from the source.
• The time complexity is O(V + E), and the space complexity is O(V).
• By adding a parent array, you can extend the algorithm to reconstruct the actual sequence of nodes in the shortest path.

Preview of the Next Lesson:
With BFS under our belt, we'll turn to the other fundamental traversal algorithm: Depth-First Search (DFS). While BFS explores widely, DFS dives deep. We will see how its recursive nature (or its iterative implementation using a stack) is perfectly suited for a different class of problems, such as detecting cycles and exploring maze-like structures.