Breadth First Search (BFS) Traversal in C++

BFS is a graph traversal method that explores all the neighbors of a node before going deeper. It’s ideal for finding the shortest path in an unweighted graph and is widely used in real-world applications like web crawling, routing, and level order traversal in trees.

Breadth First Search (BFS) Traversal on Graph

class Solution {
  public:
    vector<int> bfs(vector<vector<int>> &adj){
        queue<int> q;
        int n=adj.size();
        vector<bool> vis(n,false);
        q.push(0);
        vector<int> t;
        t.push_back(0);
        vis[0]=true;

        while(!q.empty()){
            int top=q.front();
            q.pop();
            for(int i=0;i<adj[top].size();i++){
                int top1=adj[top][i];
                if(!vis[top1]){
                    t.push_back(top1);
                    vis[top1]=true;
                    q.push(top1);
                }
            }
        }
        return t;
    }
};

int main() {
    vector<vector<int>> adj = {
        {1, 2},
        {0},
        {0}
    };

    Solution s;
    vector<int> result = s.bfs(adj);

    for(int i=0;i<result.size();i++) {
        cout << result[i] << " ";
    }
    cout << endl;
    return 0;
}

Input

Adjacency List:
0 → 1, 2 
1 → 0 
2 → 0
 Output
0 1 2

How It Works

BFS starts at node 0 and visits all its neighbors (1 and 2) first. It uses a queue to track which node to explore next. Once all neighbors are processed, it moves level by level until all reachable nodes are visited.

---

Time and Space Complexity

• Time Complexity: O(V + E)

• Space Complexity: O(V)