Iterative BFS with a Queue

The Philosophy of BFS: Exploring Level by Level

Imagine dropping a stone into a still pond. The ripples spread out in concentric circles, moving uniformly outward from the center. Breadth-First Search explores a graph in a similar manner. Starting from a source vertex s, it first visits all vertices at distance 1 from s. Then, it visits all vertices at distance 2, and so on, until all reachable vertices have been explored.

This concept of "levels" or "distance" is key. In an unweighted graph, the distance between two vertices is simply the minimum number of edges on a path connecting them.

• Level 0: The source vertex s.
• Level 1: All direct neighbors of s.
• Level 2: All unvisited neighbors of Level 1 vertices.
• Level 3: All unvisited neighbors of Level 2 vertices.
• ...and so on.

The video below from the "take U forward" channel provides an excellent visual demonstration of this level-wise traversal.

The Queue: The Engine of BFS

In the last lesson, we saw how the implicit stack of recursion was a natural fit for the backtracking nature of DFS. For the "first-in, first-out" level-wise exploration of BFS, the perfect data structure is the queue.

A queue ensures that we process vertices in the exact order we discover them. By adding the source to the queue, and then systematically dequeuing a vertex and enqueuing all its unvisited neighbors, we guarantee that we fully explore each level before any vertex from the next level is even considered.

The process is as follows:

1. Initialize a queue and add the starting vertex s to it.
2. Create a visited array (just as with DFS) and mark s as visited.
3. Loop as long as the queue is not empty:
   a. Dequeue a vertex, let's call it u.
   b. Process u (e.g., add it to our traversal list).
   c. For each neighbor v of u:
   i. If v has not been visited, mark it as visited and enqueue it.

This animated GIF provides a clear visual of this process, showing how nodes are added to the back of the "Frontier Queue" and processed from the front, building the traversal level by level.

The Algorithm in Action

Let's trace the algorithm on a more general graph. The image below provides a comprehensive snapshot of a BFS traversal starting from vertex 'a'. It shows the state of the graph, the adjacency list, the queue, the visited set, and the final traversal order.

To formalize this, cp-algorithms.com provides a concise description.

Implementing BFS in C++

Translating this algorithm into C++ is straightforward, especially since you are already familiar with the adjacency list representation and the visited array from our DFS lesson. We'll use std::vector for the adjacency list and visited array, and std::queue from the <queue> header for our queue.

The core implementation is very clean and directly mirrors the logic we've discussed.

Let's break down a slightly simplified version of that code which only performs the traversal.

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

using namespace std;

// Assumes 'adj' is a pre-filled adjacency list
vector<int> bfs(int start_node, int n, const vector<vector<int>>& adj) {
    vector<int> traversal_order;
    vector<bool> visited(n + 1, false); // Using n+1 for 1-based indexing
    queue<int> q;

    // 1. Initial setup
    q.push(start_node);
    visited[start_node] = true;

    // 2. Loop while there are nodes to process
    while (!q.empty()) {
        // 3. Dequeue a vertex and add to traversal list
        int u = q.front();
        q.pop();
        traversal_order.push_back(u);

        // 4. Enqueue all unvisited neighbors
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    return traversal_order;
}

To see a line-by-line trace of this code on an example graph, the "take U forward" channel provides another excellent walkthrough.

Complexity Analysis

The performance analysis for BFS is identical to that of DFS when using an adjacency list.

• Time Complexity: $O(V+E)$. Each vertex is enqueued and dequeued exactly once. When a vertex u is dequeued, we iterate through its neighbors. Over the entire run of the algorithm, this means we look at each edge (u,v) once when processing u and once when processing v (in an undirected graph). Thus, the total work is proportional to the sum of vertices and edges.

• Space Complexity: $O(V+E)$. This is dominated by the storage for the adjacency list. The auxiliary space required by the visited array is $O(V)$, and the queue can, in the worst case (a very "wide" graph, like a star graph), hold up to $O(V)$ vertices.

This linear time complexity makes BFS, like DFS, a highly efficient and fundamental tool for competitive programming.

Conclusion

In this lesson, you have learned the "breadth-first" approach to graph traversal. You now understand how its level-by-level exploration is naturally implemented with a queue, a FIFO data structure.

Key Takeaways:

• BFS explores "wide": It visits all nodes at a certain distance (level) before moving to the next level.
• A queue is the right tool: The FIFO nature of a queue ensures nodes are processed in the order they are discovered, facilitating level-wise traversal.
• The iterative implementation is simple: Using a while loop, a queue, and a visited array, the algorithm is concise and efficient.
• The complexity is linear: BFS runs in $O(V+E)$ time and space, making it very fast.

You now have two powerful traversal algorithms in your toolkit: the deep, recursive DFS and the wide, iterative BFS. In our next lesson, we will formally prove the most celebrated property of BFS: why it is guaranteed to find the shortest path between two nodes in any unweighted graph.