G-5. Breadth-First Search (BFS) | C++ and Java | Traversal Technique in Graphs

Breadth-First Search (BFS) is a foundational graph traversal technique that explores a graph level by level, moving outward in expanding concentric circles from a given starting node. It is an indispensable algorithm required to solve virtually all complex graph problems.

1. Why Do We Need Graph Traversals?

Unlike linear data structures (arrays, linked lists, or trees which have a definitive root and hierarchical parent-child pointer structure), general graphs can contain cycles, multiple connected components, and complex multi-directional edges.

• The Problem: You cannot simply start walking a graph without a systematic strategy, or you risk getting trapped in infinite loops or missing disconnected nodes entirely.
• The Solution: Traversal algorithms like BFS (Breadth-First Search) and DFS (Depth-First Search) provide deterministic rules to visit every vertex in a graph exactly once.

2. Core Mental Model: The Level-Wise Search Analogy

The defining characteristic of BFS is its breadth-first nature. It explores neighbors uniformly before going deeper.

Real-Life Analogy: Imagine dropping a stone in the center of a calm pond. The impact point is your starting node (Level 0). The ripples spread outward in expanding concentric circles: first touching immediate neighbors (Level 1), then moving outward to the next ring (Level 2), and so on. BFS operates on this exact distance-equality principle.

Level-Wise Progression Example

Consider an undirected graph with nodes numbered 1 through 9. If we set Node 1 as our starting point:

• Level 0: [1] (The starting anchor at distance 0)
• Level 1: [2, 6] (Direct neighbors of node 1 at distance 1)
• Level 2: [3, 4, 7, 8] (Neighbors of level 1 nodes at distance 2)
• Level 3: [5, 9] (Outer ring nodes at distance 3)

3. Impact of Changing the Starting Node

The resulting traversal sequence is entirely dependent on your starting node.

If we shift our starting node from 1 to 6, the entire distance hierarchy shifts:

Key Takeaway: BFS guarantees the shortest path in unweighted graphs because it discovers nodes in strictly increasing order of their edge distance from the source.

4. Initial Configuration for BFS

To implement BFS programmatically, two primary data structures are required alongside your graph representation:

1. A Queue Data Structure (std::queue in C++, Queue in Java): Operates on a FIFO (First-In, First-Out) principle to maintain the order of nodes to visit next.
2. A Visited Array / Vector (vector<int> visited): A boolean/integer array sized N + 1 (for 1-based indexing) or N (for 0-based indexing) to track whether a node has already been touched or added to the queue, preventing infinite loops.

Initial Setup State:

Queue: [ StartNode ]
Visited Array: [ 0, 1, 0, 0, 0, ... ] (Mark StartNode as 1 / visited)

5. Step-by-Step Algorithm Walkthrough

The execution follows an iterative loop until the queue is exhausted:

1. Pop & Print: Extract the front element from the queue. Add it to your traversal result list.
2. Scan Neighbors: Look up the current node's adjacency list to find all its direct neighbors.
3. Filter & Enqueue: For each neighbor:
   • Check if it has been marked as visited in your visited array.
   • If ** unvisited**, mark it as 1 (visited) immediately and push it into the queue.
4. Repeat: Continue the loop until queue.empty() is true.

6. Complete Flow Walkthrough Example

Let's trace how the algorithm processes nodes:

This process repeats systematically until every connected node is processed.

7. Graph Representation: Adjacency List Recap

Before coding, remember that graphs are supplied as Adjacency Lists (an array or vector of lists/vectors where index i stores all connected neighbor nodes).

8. Production-Grade Code Implementation (C++ & Java)

Below is the clean, production-ready implementation for an undirected graph using 0-based indexing.

C++ Implementation

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    // Function to return Breadth First Traversal of given graph.
    vector<int> bfsOfGraph(int V, vector<int> adj[]) {
        vector<int> bfs;
        vector<int> visited(V, 0); // Visited array initialized to 0
        
        queue<int> q;
        
        // Initial configuration: Start from node 0
        visited[0] = 1;
        q.push(0);
        
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            bfs.push_back(node);
            
            // Traverse all adjacent neighbors of the current node
            for (auto it : adj[node]) {
                if (!visited[it]) {
                    visited[it] = 1;
                    q.push(it);
                }
            }
        }
        
        return bfs;
    }
};

Java Implementation

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

class Solution {
    // Function to return Breadth First Traversal of given graph.
    public ArrayList<Integer> bfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
        ArrayList<Integer> bfs = new ArrayList<>();
        boolean[] visited = new boolean[V];
        
        Queue<Integer> q = new LinkedList<>();
        
        // Initial configuration: Start from node 0
        visited[0] = true;
        q.add(0);
        
        while (!q.isEmpty()) {
            int node = q.poll();
            bfs.add(node);
            
            // Traverse all adjacent neighbors of the current node
            for (Integer it : adj.get(node)) {
                if (!visited[it]) {
                    visited[it] = true;
                    q.add(it);
                }
            }
        }
        
        return bfs;
    }
}

Note: Although the explanation references directed/undirected graphs, this exact algorithm works seamlessly for both. In an undirected graph, edges go both ways; in a directed graph, the adjacency list naturally restricts traversal only to outward-directed edges.

9. Complexity Analysis

Time Complexity: $\mathcal{O}(N) + \mathcal{O}(2E)$

• Queue Operations ($\mathcal{O}(N)$): Every vertex/node is added to the queue and removed from the queue exactly once. Therefore, the while loop runs $N$ times.
• Degree Iteration ($\mathcal{O}(2E)$): Inside the queue loop, the inner for loop iterates over the adjacency list of each node. Across the entire graph execution, this inner loop sums up the degrees of all nodes. In an undirected graph, the sum of all degrees equals twice the number of edges ($2E$).

Space Complexity: $\mathcal{O}(3N) \approx \mathcal{O}(N)$

• Visited Array: Takes $\mathcal{O}(N)$ space.
• Queue Data Structure: In the worst-case scenario (e.g., a star graph or a wide level), the queue can hold up to $\mathcal{O}(N)$ nodes.
• BFS Result Storage Vector: Takes $\mathcal{O}(N)$ space to store the final traversal sequence.
• (Note: The adjacency list space $\mathcal{O}(N + 2E)$ is provided as input and thus excluded from auxiliary algorithm space).

10. Summary and Key Takeaways

• Level-Wise Exploration: BFS explores graphs outward in expanding concentric circles, making it ideal for finding shortest paths in unweighted graphs.
• Starting Node Sensitivity: Changing the starting node alters the distance hierarchy and the resulting traversal sequence entirely.
• Initial Configuration: Always instantiate a Queue (for FIFO node ordering) and a Visited Array (to prevent infinite cycles).
• Queue Mechanics: Pop the front element, record/print it, iterate through its unvisited neighbors, mark them visited, and push them into the queue.
• Time Complexity Balance: Runs in $\mathcal{O}(N + 2E)$ time because every node is visited once and every edge is traversed across endpoint degrees.
• Space Efficiency: Requires $\mathcal{O}(N)$ auxiliary space for the queue and visited tracking structures.
• Universal Applicability: The core BFS template applies identically to both directed and undirected graph structures.