Breadth First Search (BFS) Traversal of a Graph in C++

In this blog post, we’ll implement BFS traversal on a graph using an adjacency list representation in C++.

---

 What is BFS?

BFS starts at a given source node (usually node 0) and explores all its neighbors before moving to the next level. It uses a queue to keep track of nodes to visit.

Breadth First Search (BFS) Traversal of a Graph in C++

Problem Statement

Given an undirected graph represented as an adjacency list, perform a BFS traversal starting from node 0.

C++ Code for BFS Traversal:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
  public:
    vector<int> bfs(vector<vector<int>>&adj) {
        queue<int> q;
        int n=adj.size();
        vector<int> vis(n,0);
        q.push(0);
        vis[0]=1;
        vector<int> t;
        t.push_back(0);
        while(!q.empty()){
            int temp=q.front();
            q.pop();
            for(int i=0;i<adj[temp].size();i++){
                if(vis[adj[temp][i]]!=1){
                    vis[adj[temp][i]]=1;
                    q.push(adj[temp][i]);
                    t.push_back(adj[temp][i]);
                }
            }
        }

        return t;
    }
};

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

    Solution obj;
    vector<int>result=obj.bfs(adj);
    cout <<"BFS Traversal: ";
    for(int i=0;i<result.size();i++){
        cout<<result[i]<< " ";
    }
    cout<<endl;

    return 0;
}

Output